三沙市网站建设_网站建设公司_Spring_seo优化

1.题目

2.思路

（1）思路：
可以用dfs，深度优先遍历，但是要符合先遍历左孩子再遍历左孩子的右孩子的规则；或者先遍历右孩子再遍历右孩子的左孩子。最后把路径上的节点个数-1，就是所得的节点个数。
但是最长 ZigZag 不一定从根开始，所以不能只沿着根的一条“左-右-左…”或“右-左-右…”走到底；需要在每个节点都考虑作为起点的可能性。最常用做法是：DFS 时同时维护“当前上一步方向 + 当前长度”，并在每个节点尝试“继续交替”与“重新开始”。

（2）定义 dfs(node, dir, len)

dir=0 表示“上一步走的是左边”（所以下一步要走右才算继续）

dir=1 表示“上一步走的是右边”（所以下一步要走左才算继续）

len 表示当前 ZigZag 的边数长度。

第一个参数 node：表示“当前递归走到的节点是谁”（一个 TreeNode 对象）

第二个参数 dir：表示“到达这个 node 的上一条边方向是什么”（一个方向标记，不是节点）

第三个参数 len：表示“当前 ZigZag 的长度（边数）”

（3）ans 为什么作为全局变量

方便在 DFS 的所有分支里共享并更新最大值。

3.代码实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{intans=0;publicintlongestZigZag(TreeNoderoot){if(root==null)return0;// 从根的左边开始，长度为1条边dfs(root.left,0,1);//代表上一步的方向是向左//从根的右边开始，长度为1条边dfs(root.right,1,1);//代表上一步的方向是向右returnans;}//TreeNode node符合zigzag路线的起始节点，不一定是根节点publicvoiddfs(TreeNodenode,intdir,intlen){if(node==null)return;ans=Math.max(ans,len);if(dir==0)//上一步方向是向左,下一步要走右才算继续{dfs(node.right,1,len+1);//向右，相反方向，长度+1dfs(node.left,0,1);//向左，相同方向，重置，长度就是1}else{//上一步方向是向右,下一步要走左才算继续dfs(node.right,1,1);//向右，相同方向，重置，长度就是1dfs(node.left,0,len+1);//向左，相反方向，长度+1}}}