1372. 二叉树中的最长交错路径

发表于 | 分类于
利用DFS解决搜索问题

用时：25min

其实是比较常规的DFS类型题目，之所以用这么久是因为对边界值的判断出了问题。

从 root 出发时， 因为root 是可能没有子节点的，所以 len 值 为 0

从子节点出发，因为已经判断完字节点，算作当前节点到下一节点已经走一条长度为 1 的边 ， 所以是 1 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var longestZigZag = function(root) {
    // true left false right 
    var max = 0
    var dfs = function (node,flag,len) {
        max = Math.max(len,max)
        if (flag) {
            node.right && dfs(node.right,!flag,len + 1)
            node.left && dfs(node.left,flag,1)
        } else {
            node.left && dfs(node.left,!flag,len + 1)
            node.right && dfs(node.right,flag,1)
        }
    }
    dfs(root,true,0)
    dfs(root,false,0)
    return max
};