网站广告推广平台,企业所得税分录,seo技能培训课程,淘客请人做网站目录 题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
给我们一棵二叉树#xff0c;问我们在这棵树里能找到的最长交错路径。最长交错路径就是在二叉树里一左一右一左一右这样走#xff0c;最…目录 题目
示例
分析
代码 题目 示例 分析
给我们一棵二叉树问我们在这棵树里能找到的最长交错路径。最长交错路径就是在二叉树里一左一右一左一右这样走最长能走的路径长度是多少。
这种二叉树类的题目我们是少不了递归遍历这次递归我们需要携带参数去递归就是记录我上一次是左拐还是右拐然后每次遍历到新的节点我们都需要重新来以此节点作为路径的起始节点来递归。
例如我上一次在二叉树里是右拐那么接下来我的递归如果是左走的话我就把记录路径长度的参数1然后再次递归并且还需要多一层递归那就是路径长度从0开始重新计算的一层递归。
具体可以参考下面的代码。
代码
class Solution {
public:int res0;void digui(TreeNode* root,int flag,int temp){if(rootnullptr){resmax(res,temp);return;}//使用flag来记录上一个是往左移还是往右移if(flag0){ //flag0则表示上一次是往左移,因此接下来如果是右移的话就把记录的路径长度1digui(root-right,1,temp1);digui(root-left,0,0); //左移则表示从0开始左右交错,路径长度置0.}else{digui(root-left,0,temp1);digui(root-right,1,0);}}int longestZigZag(TreeNode* root) {if(rootnullptr) return 0;digui(root-left,0,0);digui(root-right,1,0);return res;}
};
