叶子相似的树

记住「DFS 先左后右收叶子 → 两序列比一比」,下面逐帧套它。关键是收集顺序必须是从左到右,所以递归先走左子树。

DFS 走到节点 30,它还有孩子,不是叶子,先往左子树深入。

DFS 走到节点 50,它还有孩子,不是叶子,先往左子树深入。

走到节点 60,它左右孩子都空,是叶子。把 60 追加进 左树 的叶序列。

左树 的叶序列又长一个:现在是 [60](绿色是刚收进来的 60)。

走到节点 70,它左右孩子都空,是叶子。把 70 追加进 左树 的叶序列。

左树 的叶序列又长一个:现在是 [60、70](绿色是刚收进来的 70)。

DFS 走到节点 10,它不是叶子;左子树是空的,转到右孩子 80 继续。

走到节点 80,它左右孩子都空,是叶子。把 80 追加进 左树 的叶序列。

左树 的叶序列又长一个:现在是 [60、70、80](绿色是刚收进来的 80)。

左树 整棵 DFS 走完,从左到右的叶序列定下来:[60、70、80](绿色三个叶子)。

DFS 走到节点 90,它还有孩子,不是叶子,先往左子树深入。

走到节点 60,它左右孩子都空,是叶子。把 60 追加进 右树 的叶序列。

右树 的叶序列又长一个:现在是 [60](绿色是刚收进来的 60)。

DFS 走到节点 40,它还有孩子,不是叶子,先往左子树深入。

走到节点 70,它左右孩子都空,是叶子。把 70 追加进 右树 的叶序列。

右树 的叶序列又长一个:现在是 [60、70](绿色是刚收进来的 70)。

走到节点 80,它左右孩子都空,是叶子。把 80 追加进 右树 的叶序列。

右树 的叶序列又长一个:现在是 [60、70、80](绿色是刚收进来的 80)。

右树 整棵 DFS 走完,从左到右的叶序列定下来:[60、70、80](绿色三个叶子)。

逐位比对两棵树的叶序列。第 1 位:左树是 60、右树是 60,相等,继续看下一位。

逐位比对两棵树的叶序列。第 2 位:左树是 70、右树是 70,相等,继续看下一位。

逐位比对两棵树的叶序列。第 3 位:左树是 80、右树是 80,相等,继续看下一位。

两棵树的叶序列 [60、70、80] 和 [60、70、80] 逐位都相等,所以两棵树叶子相似,返回 true。回头看,我们没有去比树的形状,只把各自的叶子从左到右拉成一条序列再比,形状再不同也不影响。

边界:单节点比根值、长度不同直接 false、空树叶序列为空。

两个追问:可同步生成叶子边比边退;DFS 天然给出从左到右顺序。