这个函数是如何遍历二叉树的？

Question

我正在应对编码挑战。我找到了解决方案，但我没有理解部分解决方案。

提示是

Given a binary tree, find the leftmost value in the last row of the tree.

Input:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Output:
7

树定义：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

这个函数有效（不是我想出来的）：

var findBottomLeftValue = function(root) {
    var result = root.val;
    var resultHeight = 0;
    (function recurse (node, height) {
        if (node === null) {
            return;
        }
        if (node.left !== null) {
            recurse(node.left, height + 1);
        }
        if (height > resultHeight) {
            result = node.val;
            resultHeight = height;
        }
        if (node.right !== null) {
            recurse(node.right, height + 1);
        }
    })(root, 1);
    return result;
};

我理解大部分内容，但坦率地说，这是我第一次看到 IIFE 在另一个函数中，所以也许这让我有点失望。

我不明白的是，假设我们从根 1 开始（使用上面的示例），它以 node 为 1 开始。由于 node.left !== null，节点现在为 2，由于 node.left !== null，它下降到 4。node.left 现在为空，它转到下一行，更新 height 和 resultHeight。然后下一行，node.right 是 null，函数结束。在我的理解中，它 从来没有 去检查节点 3、5 等。但是函数清楚地显示了正确答案。

它在解决方案的哪个位置检查节点 3、5、6 和 7？

Answer 1

如果你把正在发生的事情想象成一个堆栈，就更容易理解了。
它从值为 1 的节点开始。当它检查左节点时，它被保留为堆栈的第一项（当它再次成为堆栈的最顶层项时再次调用）
当它在第二次迭代开始时看起来像这样：

2
---
1

然后，它会一直执行并添加到堆栈，直到它检查节点 4 没有左或右节点。
此时，它看起来像这样：

4
---
2
---
1

然后，因为在值为 4 的节点上没有其他事情可做，它被从堆栈中移除，然后它从它离开 off:checking 右节点的地方开始执行堆栈的下一个最顶层它的。

我希望这能帮助您想象和理解真正发生的事情，因为这确实帮助我和一些大学同事理解二叉树。

Answer 2

您的函数在 recurse() 的第一次调用中向左下降（第 9 行）。如果对左侧节点完成，它将在第二次调用 recurse()（第 16 行）时转到右侧。

节点的顺序将是 1 -> 2 -> 4 -> (2) -> (1) -> 3 -> 5 -> 7 -> (5) -> (3) -> 6 -> (3) -> (1).

大括号中的节点显示调用堆栈减少的位置。

这个函数是如何遍历二叉树的？

How does this function traverse Binary Tree?

javascript

iife