二叉树中的最长交错路径 图解题解

这道题到底在问什么

输入

root=[50,30,·,25,80,·,·,·,·,20]

输出

3(路径 50→30→80→20,方向 左、右、左)

最优解：一步一步想明白

1. 3记住「向左 = 左孩子的向右 + 1,向右 = 右孩子的向左 + 1」,边走边用每个节点的两个值刷新最长,下面逐帧套它。
2. 4准备后序 DFS先把演示树摆出来:根 50,左边挂 30,30 下面有 25 和 80,80 下面挂 20。目标是给每个节点算出两个值:从它出发、第一步向左和第一步向右,各能延伸出多长的交错路径。
3. 5左 → 右 → 左先看什么叫交错(金色这条):50 向左到 30,再向右到 80,再向左到 20,方向一直在左右之间交替,这就是一条合法的交错路径,3 条边。
4. 6左 → 左 ✗再看反例:50 向左到 30 之后,又向左到 25,连续两步都向左、同向了,交错就断在这里。所以经过 25 的交错,只能从 30→25 这一步重新算起。
5. 7访问 50走到节点 50(紫色)。后序:先把它的左右孩子都算完,再回头合出它自己的两个值。
6. 8访问 30走到节点 30(紫色)。后序:先把它的左右孩子都算完,再回头合出它自己的两个值。
7. 9访问 25走到节点 25(紫色),它是叶子,左右都没孩子,先算它。
8. 1025:左 0、右 025 是叶子,往左、往右都走不出去,返回 (0, 0)。约定空节点是 −1,叶子的孩子都空,所以叶子拿到 −1 + 1 = 0。
9. 11访问 80走到节点 80(紫色)。后序:先把它的左右孩子都算完,再回头合出它自己的两个值。
10. 12访问 20走到节点 20(紫色),它是叶子,左右都没孩子,先算它。
11. 1320:左 0、右 020 是叶子,往左、往右都走不出去,返回 (0, 0)。约定空节点是 −1,叶子的孩子都空,所以叶子拿到 −1 + 1 = 0。
12. 1480 向左 = 1算 80 的「向左」:先走到左孩子 20,接着必须拐向右,正好是 20 的「向右」= 0;所以 80 向左 = 0 + 1 = 1。
13. 1580 向右 = 080 没有右孩子,向右一步都走不了,记 80 向右 = 0。
14. 16ans = 180 的两个值定下来:左 1、右 0(变绿)。拿它俩去刷新全局最长,当前 ans = 1。
15. 1730 向左 = 1算 30 的「向左」:先走到左孩子 25,接着必须拐向右,正好是 25 的「向右」= 0;所以 30 向左 = 0 + 1 = 1。
16. 1830 向右 = 2算 30 的「向右」:先走到右孩子 80,接着必须拐向左,正好是 80 的「向左」= 1;所以 30 向右 = 1 + 1 = 2。
17. 19ans = 230 的两个值定下来:左 1、右 2(变绿)。拿它俩去刷新全局最长,当前 ans = 2。
18. 2050 向左 = 3算 50 的「向左」:先走到左孩子 30,接着必须拐向右,正好是 30 的「向右」= 2;所以 50 向左 = 2 + 1 = 3。
19. 2150 向右 = 050 没有右孩子,向右一步都走不了,记 50 向右 = 0。
20. 22ans = 350 的两个值定下来:左 3、右 0(变绿)。拿它俩去刷新全局最长,当前 ans = 3。
21. 23答案 = 3所有节点里最大的延伸值是 50 的「向左」= 3,对应路径 50→30(左)→80(右)→20(左)。金色标出,答案就是 3 条边。回头看:一遍后序 DFS,每个节点 O(1) 合出两个值并刷新最长,整体 O(n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node):
            nonlocal ans
            if not node:
                return (-1, -1)
            ll, lr = dfs(node.left)
            rl, rr = dfs(node.right)
            left = lr + 1
            right = rl + 1
            ans = max(ans, left, right)
            return (left, right)
        dfs(root)
        return ans

#include <algorithm>
#include <climits>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution { public: int longestZigZag(TreeNode* root){ int ans=0; function<pair<int,int>(TreeNode*)> dfs=[&](TreeNode* n){ if(!n)return pair<int,int>{-1,-1}; auto L=dfs(n->left), R=dfs(n->right); int left=L.second+1, right=R.first+1; ans=max({ans,left,right}); return pair<int,int>{left,right}; }; dfs(root); return ans; } };

import java.util.*;
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; }
}
class Solution { int ans; public int longestZigZag(TreeNode root){ ans=0; dfs(root); return ans; } int[] dfs(TreeNode n){ if(n==null)return new int[]{-1,-1}; int[] L=dfs(n.left), R=dfs(n.right); int left=L[1]+1, right=R[0]+1; ans=Math.max(ans,Math.max(left,right)); return new int[]{left,right}; } }

复杂度

面试官可能追问