BST的InOrder遍历...为什么循环条件是"cur != null || !stack.empty()"？”

Question

这是 BST 的中序遍历（左、根、右）：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();

    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;

    while(cur!=null || !stack.empty()){
        while(cur!=null){
            stack.add(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
    }

    return list;
}

我想不通为什么 'while' 循环条件是 cur != null || !stack.empty().

我尤其对“cur != null”感到困惑。 为什么这是必要的？

根据 'or' 语句的逻辑，A || B 表示 A 和 B 都必须为假才能使循环中断。

所以一旦 cur == null 并且堆栈为空，循环就会中断。

为什么我们甚至需要关心 cur == null？这不是无关紧要的吗？

注：原LC问题（测试用）--https://leetcode.com/problems/binary-tree-inorder-traversal/

Answer 1

如果你只在栈不为空的情况下继续循环，循环根本不会开始，因为栈是空的。

即使使用do...while循环，“栈不为空”的条件也是不够的

考虑一棵没有左节点的树：

root
   \
    \
    node1
      \
       \
      node2

算法会将 root 添加到堆栈，然后将其弹出，然后将其添加到列表。之后，curr就是root的右节点，也就是node1。此时栈为空，但curr不为空

循环会在此时停止，这显然是不正确的。

while 循环只应在堆栈为空时停止并且没有正确的节点（即如果堆栈为空则继续或有一个正确的节点）。

Answer 2

没有 cur!=null 检查，如果你调用 inorderTraversal(null); 它会抛出 EmptyStackException.

如果您在任何 IDE 类似 Eclipse 中使用此运行，则可以使用调试功能。或者手动尝试执行简单输入 [1,null,2]。第一次迭代后，堆栈将为空，但 curr 不会为空。

BST的InOrder遍历...为什么循环条件是"cur != null || !stack.empty()"？”

InOrder traversal of BST...why is loop condition "cur != null || !stack.empty()" ?"

java

tree

traversal

tree-traversal

binary-search-tree