今天分享一个LeetCode题,题号是687,题目是最长同值路径,题目标签是树和递归,题目难度是简单。。。
这竟然是个简单题,也是六的很。
给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。
注意:两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出:
2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出:
2
注意: 给定的二叉树不超过10000个结点。树的高度不超过1000。
题目标签只有树和递归,树的递归无非就是前、中、后序遍历和层序遍历,那此题适合树的哪种遍历方式呢?
重点在递归,要知道递归是将原问题分解一个个可以解决的小问题,那就找找可以解决的小问题在哪里。如下图:
可解决的小问题
假设节点A和节点C是可以解决问题的小问题,都标记为1。
如果节点A和节点B同值,就获取节点A的标记,设为临时标记a,a=节点A的标记,如果不同值则将a=0;
如果节点C和节点B同值,也获取节点C的标记,设为临时标记c,c=节点C的标记,如果不同值则将c=0;
接着可以计算以节点B为顶点的子树的最长同值路径 a+c。
节点B标记哪个数有三种情况:
若节点B和左右子节点都不同值则被标记为1;
若节点B和左右子节点中的一个节点同值,则被标记为同值的子节点的标记值+1;
若节点B和左右子节点都同值,则被标记为俩子节点中最大的标记值+1;
然后依次解决一个一个子问题,直到原问题被解决,可以获取这棵树的最长同值路径。
后序遍历是先解决两个子节点再解决子节点的父节点,动画如下:
知道了用后序遍历可以解决一个一个小问题,从叶子节点开始,到以非叶子节点为顶点的子树,保存这个子树的最长同值路径,通过后序遍历依次解决以所有非叶子节点为顶点的小问题,直到根节点。看下面动画:
private int count;
public int longestUnivaluePath(TreeNode root) {
count = 0;
// 采用后序遍历
traverse(root);
return count;
}
private int traverse(TreeNode node) {
if (node == null) return 0;
int left = traverse(node.left);
int right = traverse(node.right);
// 合并子问题
int l = 0, r = 0;
if (node.left != null && node.left.val == node.val) l += left;
if (node.right != null && node.right.val == node.val) r += right;
count = count > l + r ? count : l + r;
return l > r ? l + 1 : r + 1;
}
做完之后,这题确实是个简单题嗷。