对于一棵由黑白点组成的二叉树，我们需要找到其中最长的单色简单路径，其中简单路径的定义是从树上的某点开始沿树边走不重复的点到树上的另一点结束而形成的路径，而路径的长度就是经过的点的数量(包括起点和终点)。而这里我们所说的单色路径自然就是只经过一种颜色的点的路径。你需要找到这棵树上最长的单色路径。
给定一棵二叉树的根节点(树的点数小于等于300，请做到O(n)的复杂度)，请返回最长单色路径的长度。这里的节点颜色由点上的权值表示，权值为1的是黑点，为0的是白点。
[编程题]树上最长单色路径
class LongestPath {
public:
int maxLen = 0; //记录最长路径值（一定要赋初值）
//获取路径长度
int getPath(TreeNode *root){
if(root == NULL){
return 0;
}
//记录左右子树最大长度
int left = 0;
int right = 0;
//处理左子树
if(root->left != NULL){
int ret = getPath(root->left); //左子树的最大长度
//如果这个节点和左子树颜色一样
if(root->val == root->left->val){
left = ret; //接收，否则没有接收
}
}
//处理右子树
if(root->right != NULL){
int ret = getPath(root->right);
if(root->val == root->right->val){
right = ret;
}
}
//记录最大长度值，包含左子树最大路径+根节点+右子树
maxLen = max(maxLen, (left+right+1));
//返回左右子树中最长的路径值
int t = max(left, right) + 1;
return t;
}
int findPath(TreeNode *root){
if(root == NULL){
return 0;
}
getPath(root);
return maxLen;
}
};
发表于 2016-04-20 14:47:52
回复(3)
一开始题目理解错了，写了好长时间，思路是后序遍历，需要两个变量，一个是左子树和右子树中高度较大的值，一个是当前最长的子路径
这个子路径是看左子树高度加右子树高度和根节点之和的最大值(前提是节点的颜色相同的情况下)
class LongestPath {
public:
int searchPath(TreeNode* node,int cur,int &max)
{
if(!node)
return 0;
int height1=1,height2=1;
if(node->left)
{
int left=searchPath(node->left,node->left->val,max);
if(node->left->val==cur)
height1+=left;
}
if(node->right)
{
int right=searchPath(node->right,node->right->val,max);
if(node->right->val==cur)
height2+=right;
}
max=(height1+height2-1)>max?(height1+height2-1):max;
return height1>height2?height1:height2;
}
int findPath(TreeNode* root) {
// write code here
if(!root)
return 0;
int max=0;
int height=searchPath(root,root->val,max);
return max;
}
};
发表于 2016-04-20 12:42:32
回复(0)
和楼上老兄一样，题目意思开始理解错了，以为路径一直是从上到下走的，哎。。。这题跪了啊。
今天看到题目解答才发现原来路径是可以通过从左子树到右子树的，现在想想悔恨不已啊！就差那么一点了。
下面是解题思路：
后序遍历，路径无非是从左节点到当前节点到右节点（颜色相同），或者从当前节点到左右子树。
只要在后序遍历的基础上增加一些判断就可以了。
public int findPath(TreeNode root)
{
order(root);
if (root == null)
return 0;
else
return maxLength;
}
public int order(TreeNode root) {
// write code here
if (root == null) {
return 0;
} else {
int leftLength = order(root.left);
int rightLength = order(root.right);
int length = 1;
if (root.left == null && root.right == null) {
length = 1;
maxLength = Math.max(length, maxLength);
}
else {
if (root.left != null && root.val == root.left.val)
length += leftLength;
if (root.right != null && root.val == root.right.val)
length = Math.max(length, 1 + rightLength);
if (root.left == null || root.right == null) {
maxLength = Math.max(length, maxLength);
} else {
if (root.right.val == root.left.val && root.val == root.left.val)
maxLength = Math.max(maxLength, leftLength + rightLength + 1);
else
maxLength = Math.max(length, maxLength);
}
}
return length;
}
}
int maxLength = 0;
发表于 2016-04-20 14:51:51
回复(0)
超级简洁的Python实现
在递归中每次返回当前节点的最大高度，在递归之外记录一个出现过的最大长度。
class LongestPath: def __init__(self): self.maxlong = 0 #用来记录递归过程中出现过的最大长度 def findPath(self, root): self.findeach(root) return self.maxlong #返回最终结果 def findeach(self, root): if root.left is not None: x = self.findeach(root.left) #只要左子树不为空就递归一次 ml = x if root.left.val == root.val else 0 else: ml = 0 #ml是左子树的最大高度，颜色不同则为0 if root.right is not None: y = self.findeach(root.right) mr = y if root.right.val == root.val else 0 else: mr = 0 maxhigh = max(ml,mr)+1 #当前节点的最大高度 maxlong = ml+mr+1 #左子树高度+右子树高度+1=当前节点最大路径长度 if maxlong>self.maxlong: self.maxlong = maxlong #更新最大长度 return maxhigh
编辑于 2020-02-21 22:13:27
回复(0)
public class LongestPurePath {
/**
* @param args
*/
int maxLen = 0;
public int findPath(TreeNode root) {
// write code here
if(root == null){
return 0;
}
getPath(root);
return maxLen;
}
//获取左右子树中最长的路径值
public int getPath(TreeNode root) {
if(root == null){
return 0;
}
//记录左右子数的最大路径长度
int left = 0;
int right = 0;
if(root.left!=null){
int len = getPath(root.left); //左子树的最大长度
if(root.val == root.left.val){ //颜色相同
left = len;
}
}
if(root.right!=null){
int len = getPath(root.right); //左子树的最大长度
if(root.val == root.right.val){ //颜色相同
right = len;
}
}
maxLen = Math.max(maxLen, left+right+1); //记录最大长度值，包含左子树最大路径+根节点+右子树
return Math.max(left, right) + 1; //返回左右子树中最长的路径值
}
}
发表于 2016-09-29 10:55:02
回复(0)
题目的意思应该是如上图所示，可以沿着树枝走。
考试的时候没想出来，后来回去想了想，做出来了，下面说下我的思路。
用一个数组res保存所有路径长度的结果。
如果当前节点为叶子节点，就将现在记录的长度压入res；
如果当前节点的子节点与当前节点的值不同，也将现在的记录长度压入res，同时将子节点的记录长度置1；
如果当前节点只有一个子节点与当前节点的值相同，将纪录长度+1；
如果当前节点两个子节点与当前节点的值相同，将出现上同所示的情况，将两节点的纪录长度置1，求出两子节点对应的最大单色深度路径长度，相加之后再加1，压入res中；
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class LongestPath {
vector<int> res;
void helper(TreeNode* root,vector<int> &res,int
listlenth){
if(root == NULL) res.push_back(listlenth);
int val = root -> val;
if(root -> left == NULL && root -> right ==
NULL){
res.push_back(listlenth );
}else{
if(root -> right == NULL){
if(root -> left -> val == val){
helper(root-> left,res,listlenth+1);
}else{
res.push_back(listlenth);
helper(root -> left,res,1);
}
}else if(root -> left == NULL){
if(root -> right -> val == val){
helper(root -> right,res,listlenth+1);
}else{
res.push_back(listlenth);
helper(root -> right,res,1);
}
}else{
if(root -> right -> val != val &&
root -> left -> val !=val){
res.push_back(listlenth);
helper(root -> right,res,1);
helper(root -> left,res,1);
}else if(root -> right -> val !=val){
helper(root -> left,res,listlenth+1);
helper(root -> right,res,1);
}else if(root -> left -> val !=val){
helper(root -> right,res,listlenth+1);
helper(root -> left,res,1);
}else{
helper(root -> left,res,listlenth+1);
helper(root -> right,res,listlenth+1);
vector<int> leftdd;
vector<int> rightdd;
helper(root -> left,leftdd,1);
helper(root -> right,rightdd,1);
int ll = rightdd[0]+leftdd[0]+1;
res.push_back(ll);
}
}
}
}
public:
int findPath(TreeNode* root) {
// write code here
if(root == NULL) return 0;
helper(root,res,1);
int max = 0;
for(int i = 0;i < res.size();++i){
max = res[i] > max ? res[i]:max;
}
return max;
}
};
编辑于 2016-04-20 10:06:36
回复(2)
一颗树的最长单色路径 = 左子树的最长单色路径 + 右子树的最长单色路径 + 1
如果左子树的颜色和根不一样，那么左子树的最长单色路径为 0
如果右子树的颜色和根不一样，那么右子树的最长单色路径为0
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class LongestPath {
public:
int longestPath = 0;
int findPath(TreeNode* root) {
// write code here
dfs(root);
return longestPath;
}
int dfs(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int lP = dfs(root->left);
int rP = dfs(root->right);
if (root->left == nullptr || root->left->val != root->val) {
lP = 0;
}
if (root->right == nullptr || root->right->val != root->val) {
rP = 0;
}
longestPath = max(lP + rP + 1, longestPath);
return max(lP, rP) + 1;
}
};
发表于 2023-03-22 11:38:20
回复(0)
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class LongestPath {
public:
int res;
int func(TreeNode* root){
if(root == nullptr) return 0;
int leftPath = func(root->left);
int rightPath = func(root->right);
int num = 0;
if(root->left && root->right && root->val == root->left->val && root->val == root->right->val){
num = leftPath + rightPath + 1;
if (num > res) res = num;
return max(leftPath, rightPath) + 1;
}else if(root->left && root->val == root->left->val){
num = leftPath + 1;
}else if(root->right && root->val == root->right->val){
num = rightPath + 1;
}else{
num = 1;
}
if (num > res) res = num;
return num;
}
int findPath(TreeNode* root) {
res = 0;
func(root);
return res;
}
};
发表于 2022-08-05 00:23:51
回复(0)
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class LongestPath {
private:
int maxn;
public:
LongestPath(){
maxn=0;
}
int findPath(TreeNode* root) {
Traverse(root);
return maxn;
}
int max(int a,int b){
return a>b?a:b;
}
int min(int a,int b){
return a<b?a:b;
}
int* Traverse(TreeNode* root){
int* result=new int[3];
result[0]=0;result[1]=0;result[2]=0;
if(root==NULL)
return result;
int* left=Traverse(root->left);
int* right=Traverse(root->right);
int index=root->val;
result[index]=max(left[index],right[index])+1;
result[2]=result[index]+min(left[index],right[index]);
if(maxn<result[2])
maxn=result[2];
return result;
}
};
发表于 2020-02-22 11:24:15
回复(0)
后序遍历，递归返回左右子树较大长度
当前节点计算左右子树长度和，与最大值比较
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class LongestPath {
int maxLen=0;
public int findPath(TreeNode root) {
// write code here
if(root == null)
return 0;
getPath(root);
return maxLen;
}
public int getPath(TreeNode root) {
// write code here
if(root==null)
return 0;
int left = getPath(root.left); //左子树的最大长度
if(left!=0 && root.val!=root.left.val)
left=0;
int right = getPath(root.right); //左子树的最大长度
if(right!=0 && root.val!=root.right.val)
right=0;
//计算最大值
int Len=left+right+1;
maxLen=maxLen>Len?maxLen:Len;
//返回左右子树最大长度
return (Math.max(left, right) + 1);
}
}
发表于 2019-09-05 10:46:38
回复(0)
使用了层次遍历的逆序。代码比后序遍历的要长
class LongestPath {
public:
int findPath(TreeNode* root) {
// write code here
int maxans=-1;
int ansarr[300];
vector<TreeNode *> vec;
vec.push_back(root);
int i=0;
for(int i=0;i<vec.size();++i)
{
if(vec[i]->left!=NULL)
vec.push_back(vec[i]->left);
if(vec[i]->right!=NULL)
vec.push_back(vec[i]->right);
}
for(int i=vec.size()-1;i>=0;--i)
{
int tmp =vec[i]->val; //1:0
int leftblack,leftwhite,rightblack,rightwhite,white,black;
if(vec[i]->left==NULL)
leftblack=leftwhite=0;
else
{
leftblack =vec[i]->left->val>>16;
leftwhite =vec[i]->left->val&0x0000FFFF;
}
if(vec[i]->right==NULL)
rightblack=rightwhite=0;
else
{
rightblack =vec[i]->right->val>>16;
rightwhite =vec[i]->right->val&0x0000FFFF;
}
if(tmp==1)
{
black=(int)max(leftblack,rightblack)+1;
maxans=leftblack+rightblack+1>maxans?leftblack+rightblack+1:maxans;
white=0;
}
else if(tmp==0)
{
white=(int)max(leftwhite,rightwhite)+1;
maxans=leftwhite+rightwhite+1>maxans?leftwhite+rightwhite+1:maxans;
black=0;
}
tmp=black<<16;
tmp+=white;
vec[i]->val=tmp;
}
return maxans;
}
};
发表于 2017-02-14 15:53:44
回复(0)
import java.util.*;
/**
* 对@geassdai的代码进行了解释
* 从根节点分别往下递归,可以先从左子树往下走,在递归右子树
*/
public class LongestPath {
int max_path = 0;//最终的结果
int max_len = 0;//单个子树的长度
int len = 0;//临时的路径
public int findPath(TreeNode root) {
if (root == null)
return 0;
setmaxpath(root);
int tem = max_path;
max_path = 0;
max_len = 0;
return tem;
}
public void setmaxpath(TreeNode root) {
if (root == null)
return;
int l;//左子树
if (root.left != null && root.val == root.left.val) {
len = 1;
maxlen(root.left);
l = max_len;
max_len = 0;
} else {
l = 0;
}
System.out.println("l=" + l);
int r;//从右子树开始往下走
if (root.right != null && root.val == root.right.val) {
len = 1;
maxlen(root.right);
r = max_len;
max_len = 0;
} else {
r = 0;
}
System.out.println("r=" + r);
if (l + 1 + r > max_path)//加一是因还要把根节点加进去
max_path = l + 1 + r;
setmaxpath(root.left);
setmaxpath(root.right);
}
public void maxlen(TreeNode root) {
if (root == null)
return;
if (root.left != null && root.val == root.left.val) {
len++;
maxlen(root.left);
} else if (root.right != null && root.val == root.right.val) {
len++;
maxlen(root.right);
} else if (len > max_len) {
max_len = len;
len = 0;
}
// return 0;
}
}
发表于 2016-09-11 11:15:57
回复(0)
# -*- coding:utf-8 -*-
#coding=utf-8
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class LongestPath:
def getPath(self,root): ###返回以root为根节点的树中的最长路径（最长相同颜色的节点路径）和最长单向路径（以root为末节点的一条路径）
if(root==None):
return 0,0;
cur_MaxLen=1;
cur_MaxOneSide=1;
left_maxLen,right_maxLen=0,0;
if(root.left):
left_maxLen,left_maxOneSide=self.getPath(root.left);
if(root.left.val==root.val):
cur_MaxLen+=left_maxOneSide;
cur_MaxOneSide=max(cur_MaxOneSide,left_maxOneSide+1);
if(root.right):
right_maxLen,right_maxOneSide=self.getPath(root.right);
if(root.right.val==root.val):
cur_MaxLen+=right_maxOneSide;
cur_MaxOneSide=max(cur_MaxOneSide,right_maxOneSide+1);
return max([cur_MaxLen,left_maxLen,right_maxLen]),cur_MaxOneSide;
def findPath(self,root):
return self.getPath(root)[0];
编辑于 2016-09-09 00:02:54
回复(0)
class LongestPath {
public:
int help(TreeNode *root,int &res){//求包含根节点root的最长单色路径，res是最终结果
if(root==NULL)
return 0;
int left=help(root->left,res);//包含左子树根节点的最长单色路径
int right=help(root->right,res);//包含右子树根节点的最长单色路径 if(root->left&&root->right){
if(root->val==root->left->val&&root->val==root->right->val){
int t=left+right+1;
if(t>res)
res=t;
return left>right?left+1:right+1;
}
else if(root->val==root->left->val){
int t=left+1>right?left+1:right;
if(t>res)
res=t;
return left+1;
}
else if(root->val==root->right->val){
int t=right+1>left?right+1:left;
if(t>res)
res=t;
return right+1;
}
else{
return 1;
}
}
else if(root->left){
if(root->val==root->left->val){
int t=left+1;
if(t>res)
res=t;
return left+1;
}
else{
return 1;
}
}
else if(root->right){
if(root->val==root->right->val){
int t=right+1;
if(t>res)
res=t;
return right+1;
}
else{
return 1;
}
}
else{
return 1;
}
}
int findPath(TreeNode* root) {
// write code here
if(root==NULL)
return 0;
int res=1;
help(root,res);
return res;
}
};
发表于 2016-09-05 16:51:00
回复(0)
importjava.util.*;/*public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}*/publicclassLongestPath {intmax_path=0,max_len=0,len=0;publicintfindPath(TreeNode root){if(root==null)return0;setmaxpath(root);inttem = max_path;max_path = 0; max_len = 0;returntem;}publicvoidsetmaxpath(TreeNode root){if(root==null) return;intl ;if(root.left!=null&&root.val==root.left.val){len=1;maxlen(root.left);l=max_len;max_len=0;}elsel = 0;System.out.println("l="+l);intr;if(root.right!=null&&root.val==root.right.val){len=1;maxlen(root.right);r=max_len;max_len=0;}elser = 0;System.out.println("r="+r);if(l+1+r>max_path) max_path = l+1+r;setmaxpath(root.left);setmaxpath(root.right);}publicvoidmaxlen(TreeNode root){if(root==null) return;if(root.left!=null&&root.val==root.left.val){len++;maxlen(root.left);}elseif(root.right!=null&&root.val==root.right.val){len++;maxlen(root.right);}elseif(len>max_len){max_len = len;len = 0;}//return 0;}}
发表于 2016-04-27 16:06:38
回复(0)
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class LongestPath:
def findPath(self, root):
# write code here
self.max = 0
self.read_each_node(root)
return self.max
def read_each_node(self, node):
if node.left is not None:
lb, lw = self.read_each_node(node.left)
else:
lb, lw = 0,0
if node.right is not None:
rb, rw = self.read_each_node(node.right)
else:
rb, rw = 0,0
if node.val == 0: # 白色
w = 1
b = 0
else: # 黑色
w = 0
b = 1
if w:
node.b = 0
if lw > 0 and rw > 0:
node.sub_w = lw + rw + w
if node.sub_w > self.max:
self.max = node.sub_w
if lw > rw:
node.w = lw + 1
else:
node.w = rw + 1
else:
node.sub_w = 0 # 没有利用价值
if lw > 0:
node.w = lw + 1
elif rw > 0:
node.w = rw + 1
else:
node.w = 1
if node.w > self.max:
self.max = node.w
else:
node.w = 0
if lb > 0 and rb > 0:
node.sub_b = lb + rb + b
if node.sub_b > self.max:
self.max = node.sub_b
if lb > rb:
node.b = lb + 1
else:
node.b = rb + 1
else:
node.sub_b = 0 # 没有利用价值
if lb > 0:
node.b = lb + 1
elif rb > 0:
node.b = rb + 1
else:
node.b = 1
if node.b > self.max:
self.max = node.b
return node.b, node.w
发表于 2016-04-27 11:01:34
回复(0)
/*
本体难点在于考虑左子树+中间节点+右子树
*/
class LongestPath {
public:
int findPath(TreeNode* root) {
// write code here
int sum = 0;
myFindPath(root,sum);
return sum;
}
int myFindPath(TreeNode *root,int &sum)
{
int left = 1,right = 1;
if(root->left)
{
left += myFindPath(root->left,sum);
if(root->left->val != root->val) left = 1;
}
if(root->right)
{
right += myFindPath(root->right,sum);
if(root->right->val != root->val) right=1;
}
sum = max(sum,left+right-1);
return left>right?left:right;
}
};
发表于 2016-04-22 14:43:02
回复(0)
class LongestPath {public:int max=0;int f(TreeNode* root){if(root==NULL){return 0;}if(root->left==NULL&&root->right==NULL){return 1;}intl=f(root->left);intr=f(root->right);if(root->left&&root->right&&root->left->val==root->val&&root->right->val==root->val){intt=l+r+1;max=max>t?max:t;return l>r?l+1:r+1;}else if(root->left&&root->right&&root->left->val!=root->val&&root->right->val!=root->val){intt=l>r?l:r;max=max>t?max:t;return 1;}else if(root->left&&root->left->val==root->val){intt=l+1;max=max>t?max:t;max=max>r?max:r;return t;}else if(root->right&&root->right->val==root->val){intt=r+1;max=max>t?max:t;max=max>l?max:l;return t;}else{intt=l>r?l:r;max=max>t?max:t;return 1;}}int findPath(TreeNode* root) {// write code heref(root);return max;}};
编辑于 2016-04-21 19:04:41
回复(0)
class LongestPath {public:void find(TreeNode* cur, TreeNode *pre, int height, int& maxlength) {if(cur == nullptr) {maxlength = max(height, maxlength);return;}if(cur->val == pre->val) {find(cur->left, cur, height + 1, maxlength);find(cur->right, cur, height + 1, maxlength);}else{maxlength = max(height, maxlength);find(cur->left, cur, 1, maxlength);find(cur->right, cur, 1, maxlength);}}int findPath(TreeNode *root) {int maxlength = 0;find(root, root, 0, maxlength);return maxlength;}};
编辑于 2016-04-20 14:42:03
回复(0)
class LongestPath {
private:
int res;
public:
int findPath(TreeNode* root) {
if(root==NULL) return 0;
res=0;
int black,white;
black=white=0;
helper(root,black,white);
return res;
}
void helper(TreeNode* root,int &black,int &white){
if(root->left==NULL && root->right==NULL){
if(root->val==0) black=1,white=0;
else black=0,white=1;
}
else {
int
lb=0,lw=0,rb=0,rw=0;//这些变量的初始化，最好在定义处就初始化，否则，其值是未定义的
if(root->left!=NULL){//注意看，这是后序处理手法，左右根
helper(root->left,lb,lw);
}
if(root->right!=NULL){
helper(root->right,rb,rw);
}
if(root->val==0){
res=res>lb+rb+1?res:lb+rb+1;white=0;
black= max(lb,rb)+1;
}
else{
res=res>lw+rw+1?res:lw+rw+1;black=0;
white= max(lw,rw)+1;
}
}
}
};
发表于 2016-04-20 00:17:41
回复(0)
问题信息
通过挑战的用户
-
2023-02-20 08:36:13
-
2023-01-04 15:40:15 -
2022-11-01 17:06:51 -
2022-10-01 15:13:43
-
2022-09-23 05:21:30
相关试题
-
评论(29) 来自“一战通offer”互联...
-
评论(31) 来自“一战通offer”互联...
-
评论(383) 来自“一战通offer”互联...
-
评论(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
