二叉树中的最长交错路径

记住「向左 = 左孩子的向右 + 1,向右 = 右孩子的向左 + 1」,边走边用每个节点的两个值刷新最长,下面逐帧套它。

先看这棵树：先把演示树摆出来:根 50,左边挂 30,30 下面有 25 和 80,80 下面挂 20。目标是给每个节点算出两个值:从它出发、第一步向左和第一步向右,各能延伸出多长的交错路径。

什么是交错路径：先看什么叫交错(金色这条):50 向左到 30,再向右到 80,再向左到 20,方向一直在左右之间交替,这就是一条合法的交错路径,3 条边。

同向就断：再看反例:50 向左到 30 之后,又向左到 25,连续两步都向左、同向了,交错就断在这里。所以经过 25 的交错,只能从 30→25 这一步重新算起。

到达 50：走到节点 50(紫色)。后序:先把它的左右孩子都算完,再回头合出它自己的两个值。

到达 30：走到节点 30(紫色)。后序:先把它的左右孩子都算完,再回头合出它自己的两个值。

到达 25：走到节点 25(紫色),它是叶子,左右都没孩子,先算它。

算出 25：25 是叶子,往左、往右都走不出去,返回 (0, 0)。约定空节点是 −1,叶子的孩子都空,所以叶子拿到 −1 + 1 = 0。

到达 80：走到节点 80(紫色)。后序:先把它的左右孩子都算完,再回头合出它自己的两个值。

到达 20：走到节点 20(紫色),它是叶子,左右都没孩子,先算它。

算出 20：20 是叶子,往左、往右都走不出去,返回 (0, 0)。约定空节点是 −1,叶子的孩子都空,所以叶子拿到 −1 + 1 = 0。

80 往左：算 80 的「向左」:先走到左孩子 20,接着必须拐向右,正好是 20 的「向右」= 0;所以 80 向左 = 0 + 1 = 1。

80 往右：80 没有右孩子,向右一步都走不了,记 80 向右 = 0。

80 刷新 ans：80 的两个值定下来:左 1、右 0(变绿)。拿它俩去刷新全局最长,当前 ans = 1。

30 往左：算 30 的「向左」:先走到左孩子 25,接着必须拐向右,正好是 25 的「向右」= 0;所以 30 向左 = 0 + 1 = 1。

30 往右：算 30 的「向右」:先走到右孩子 80,接着必须拐向左,正好是 80 的「向左」= 1;所以 30 向右 = 1 + 1 = 2。

30 刷新 ans：30 的两个值定下来:左 1、右 2(变绿)。拿它俩去刷新全局最长,当前 ans = 2。

50 往左：算 50 的「向左」:先走到左孩子 30,接着必须拐向右,正好是 30 的「向右」= 2;所以 50 向左 = 2 + 1 = 3。

50 往右：50 没有右孩子,向右一步都走不了,记 50 向右 = 0。

50 刷新 ans：50 的两个值定下来:左 3、右 0(变绿)。拿它俩去刷新全局最长,当前 ans = 3。

最长交错路径：所有节点里最大的延伸值是 50 的「向左」= 3,对应路径 50→30(左)→80(右)→20(左)。金色标出,答案就是 3 条边。回头看:一遍后序 DFS,每个节点 O(1) 合出两个值并刷新最长,整体 O(n)。

边界:单节点 0;全同向链只算 1;完美之字形链全算。

两个追问:返回两值因父亲两种接法都可能;也可自顶向下传方向与长度。