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

题目描述： 给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下： 选择二叉树中 任意 节点和一个方向（左或者右）。 如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。 改变前进方向：左变右或者右变左。 重复第二步和第三步，直到你在树中无法继续移动。 交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。 请你返回给定树中最长 交错路径 的长度。

示例 1： 输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1] 输出：3 解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。

示例 2： 输入：root = [1,1,1,null,1,null,null,1,1,null,1] 输出：4 解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。

示例 3： 输入：root = [1] 输出：0

提示： 每棵树最多有 50000 个节点。 每个节点的值在 [1, 100] 之间。

方法1： 主要思路： （1）后序遍历； （2）对于每个结点，标识当前结点是左结点还是右结点； （3）若当前结点是右结点，则需要使用一个变量保存该节点的右子树下的深度，同时返回当前结点的左子树的深度加1作为父节点的深度； （4）对于当前结点是左结点，类似； （5）则对于根节点，在确定左子树或右子树下的最大深度之后，再和之前遍历过程中保存的所有子节点中可能的最大深度比较，返回最大深度；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
          
   
public:
	//变量 is_right 标识当前结点是左结点还是右结点，res存储遍历过程中，可能出现的最大深度
    int find_depth(TreeNode*root,bool is_right,int&res){
          
   
        if(root==NULL){
          
   
            return 0;
        }
        //找出左右子树的交叉深度
        int right_depth=find_depth(root->right,true,res);
        int left_depth=find_depth(root->left,false,res);
        if(is_right){
          
   //若当前结点是右结点
            res=max(res,right_depth);//保存当前结点的右子树的最大交叉深度
            return left_depth+1;//返回父节点的交叉深度，既需要和当前结点的左子树配合
        }
        else{
          
   
            res=max(res,left_depth);
            return right_depth+1;
        }
    }
    int longestZigZag(TreeNode* root) {
          
   
        if(root==NULL||(root->left==NULL&&root->right==NULL)){
          
   //处理特殊的情形
            return 0;
        }
        int res=0;//保存子树中的最大深度
        //左右子树的交叉深度
        int left_depth=find_depth(root->left,false,res);
        int right_depth=find_depth(root->right,true,res);
        return max(res,max(left_depth,right_depth));//返回最大值
    }
};