Day106 | 灵神 | 二叉树二叉树中的最长交错路径

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

笔者题解

思路：

这道题挺难想的，笔者第一次写，没写出来，原因是情况少了，只考虑可以往左的时候往左和可以往右走的时候往右，少了不可以往左的时候往左和不可以往右的时候往右走

所以就是分四种情况，同时我们使用一个bool值flag记录上一次我们是从左边来的还是从右边来的，同时使用len记录路径长度，dfs含义就是深度搜索，但是要在搜索过程中记录最大值

规定flag为0，表示可以往左走，不可以往右走，表示我们上次走的右子树到达了本节点

flag为1，表示可以往右走，不可以往左走，表示我们上次走的左子树到达了本节点

1	void dfs(TreeNode *t,bool flag,int len)

1.可以往左的时候往左

1 2	if(!flag) dfs(t->left,1,len+1);

flag为0，这说明我们可以往左走，然后下一层的递归函数就不可以往左走只可以往右走，所以传入1，并且长度为原来长度加上本层节点就是len+1

2.可以往右走的时候往右

1 2	if(flag) if(t->right) dfs(t->right,0,len+1);

flag为1，那说明我们可以往右走，然后下一层的递归函数就不可以往右走只能往左走，所以传入0，并且长度为原来长度加上本层节点就是len+1

3.不可以往右的时候往右走

1 2	if(!flag) dfs(t->right,0,1);

flag为0，这说明我们可以往左走。但是我们没选择往左走，而是往右走了，可是这样就不符合题意了。那没办法了只能把前面积累的长度都清空然后从当前结点重新算了

所以我们这次选择往右走，所以下一层递归函数不可以往右，传入0，长度从当前节点重新计算，所以传入1

4.不可以往左的时候往左

1 2	if(flag) dfs(t->left,1,1);

flag为1，这说明我们可以往右走。但是我们没选择往右走，而是往左走了，可是这样就不符合题意了。那没办法了只能把前面积累的长度都清空然后从当前结点重新算了

所以我们这次选择往左走，所以下一层递归函数不可以往左，传入1，长度从当前节点重新计算，所以传入1

完整代码：

class Solution {
public:
    int maxLength=0;
    void dfs(TreeNode *t,bool flag,int len)
    {
        maxLength=max(maxLength,len);
        if(!flag)
        {
            if(t->left) dfs(t->left,1,len+1);
            if(t->right) dfs(t->right,0,1);
        }
        else
        {
            if(t->left) dfs(t->left,1,1);
            if(t->right) dfs(t->right,0,len+1);
        }
    }
    int longestZigZag(TreeNode* root) {
        dfs(root,0,0);
        dfs(root,1,0);
        return maxLength;
    }
};

大佬解法

这是笔者自己的理解

用l和r记录长度，l就是上层结点走左子树来到本节点的长度，r就是上层结点走右子树来到本节点的长度

如果我们在本层结点想走左子树，那么下一层的l就是r+1，r就是0

l=r+1的原因是，我们上一次走的右子树那么在本层节点才可以走左子树

r=0的原因是，我们是走的左子树，所以从右子树去的路径长度就归0了

同理，如果我们本层结点想走右子树，下一层的l就是0，r就是l+1

这个可行在于，一个节点没办法被父节点既选择向左又选择向右，要么跟随父节点向左，那就+1，要么自己向右，那就从0开始，反之亦然

class Solution {
public:
    int res = 0;
    void dfs(TreeNode* t, int l, int r){
        res=max(res,max(l,r));
        if(t==nullptr)  
            return;
        if(t->left)
            dfs(t->left,r+1,0);
        if(t->right)
            dfs(t->right,0,l+1);
    }
    int longestZigZag(TreeNode* root) {
        dfs(root,0,0);
        return res;
    }
};