Binary Search Tree Inorder遍历看不懂的解决办法

Question

嗨，我目前正在关注 leetcode 面试问题，我有这个有效的解决方案，但我无法理解两件事

解决方案代码

public class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        Stack < TreeNode > stack = new Stack < > ();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

我添加了一张图片来参考树中的值以供解决 [1]: https://i.stack.imgur.com/CqN9Q.png

我不明白的是 while 循环直到 curr 不为空或堆栈为空但是当我们向下遍历左侧时我们到达结束然后打破内循环，pop stack = curr，添加到列表和然后等于 curr.right.

那是我不明白的？在所附的图像中，最左边的节点值为 4，它没有子节点，这意味着它的右子节点将等于 null 然后打破外部 while 循环结束解决方案？

第二个问题，时间复杂度在解决方案中是 O(n)，但它不会是 O(n) 的平方，因为我们有一个循环中的循环吗？

感谢所有帮助指出我不完全理解的地方

谢谢:)

Answer 1

理解这一点的一个有用方法是通过 dry-运行代码。对于您提供的示例，跟踪如下。

Initially curr = 1

We enter the outer while loop. And we won't exit from it unless both curr = null and the stack is empty.

Because of the inner while we reach the leftmost leaf node. curr = 4

The next iteration of the inner loop causes curr to be null so we break out from it. At this point 4 is popped from the stack and inserted in the list.

curr goes to the right child of 4, which is null.

In the next iteration of outer loop, curr is null. However, since the stack is still not empty we still enter the outer loop once again. We don't enter the inner loop however since curr is null.

We pop an element from the stack. This time it being 2. Remember stack is LIFO (Last in first out)

至于整体时间复杂度。两个嵌套循环不一定转化为二次复杂度。总体复杂度仍然是 O(n)，因为树中的每个节点最多被访问一次。

Binary Search Tree Inorder遍历看不懂的解决办法

Binary Search Tree Inorder traversal cant understand solution

java

binary-tree

inorder