利用好树的后序遍历
计算最长交错路径,我们可以用每个节点的子节点的结果来计算当前节点的结果。
这也就需要用到后序遍历
定义函数
int[] getZigZag(TreeNode root)
参数 root 表示 当前位于哪一个节点
返回值为 int[],
其中[0]为当前节点向左走的最长交错路径
[1]为当前节点向右走的最长和交错路径
要求是交错路径,
所以当前节点向左走的值 必然为其左节点向右走的值 +1
所以 parent[0]= leftchild[1]+1;
同理 parent[1]=rightchild[0]+1;
最后是边界情况的处理,
当前节点为空节点的时候,应该返回[-1,-1]
时间复杂度
O(n) n 为树的节点个数
Java 代码
class Solution {
int res=0;
public int longestZigZag(TreeNode root) {
getZigZag(root);
return res;
}
private int[] getZigZag(TreeNode root){
if(root==null){
return new int[]{-1,-1};
}
int []left=getZigZag(root.left);
int []right=getZigZag(root.right);
int l=left[1]+1;
int r=right[0]+1;
res=Math.max(res,Math.max(l,r));
return new int[]{l,r};
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla