无法在 BST 中进行前序遍历

Question

问题：给定二叉树的根，return其节点值的前序遍历。

我用迭代的方式解决了这个问题，我用 'top.state++' 代替了 'state++'，我得到了答案。但是当我使用 'state++' 时无法得到答案。谁能告诉我为什么会这样？

class Solution {
    class Pair {
        TreeNode root;
        int state;
        Pair(TreeNode root,int state) {
            this.root = root;
            this.state = state;
        }
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> al = new ArrayList<>();
        if(root == null) return al;
        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(root,1));
        while(!stack.isEmpty()) {
            Pair top = stack.peek();
            int state = top.state;
            TreeNode curr = top.root;
            
            if(state == 1) {
                al.add(curr.val);
                top.state++; // why top.state++, why not state++ ?
                if(curr.left != null) stack.push(new Pair(curr.left,1));
            }
            else if(state == 2) {
                top.state++;
                if(curr.right != null) stack.push(new Pair(curr.right,1));
            }
            else {
                stack.pop();
            }
        }
       return al;
    }
}

Answer 1

因为int state = top.state是一个局部变量，复制了top.state的值。它不共享内存中的相同位置。因此，改变局部变量的值不会改变top.state字段的值。

查看此内容了解更多信息https://java-programming.mooc.fi/part-5/3-primitive-and-reference-variables

Declaring a primitive variable causes the computer to reserve some memory where the value assigned to the variable can be stored. The size of the storage container reserved depends on type of the primitive. In the example below, we create three variables. Each one has its own memory location to which the value that is assigned is copied.

int first = 10;
int second = first;
int third = second;
System.out.println(first + " " + second + " " + third);
second = 5;
System.out.println(first + " " + second + " " + third);

打印：

10 10 10
10 5 10

The name of the variable tells the memory location where its value is stored. When you assign a value to a primitive variable with an equality sign, the value on the right side is copied to the memory location indicated by the name of the variable. For example, the statement int first = 10 reserves a location called first for the variable, and then copies the value 10 into it.

Similarly, the statement int second = first; reserves in memory a location called second for the variable being created and then copies into it the value stored in the location of variable first.

Answer 2

您需要维护 pair 对象中的 state 变量。每次使用 state++ 通过循环重新分配此值，因此它不起作用。

但是我不明白为什么你需要一个 Pair 对象来进行这个遍历。简单方法：

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                result.add(root.val);
                stack.push(root);
                root = root.left;
            } else {
                TreeNode pop = stack.pop();
                root = pop.right;
            }
        }
        return result;
    }

Answer 3

你太辛苦了。找到迭代算法的一个好方法是从递归版本开始并进行转换。

void preorder(TREE t) {
  if (t != null) {
    list.add(t.val);
    preorder(t.left);
    preorder(t.right);
  }
}

假设 Java 有 goto。我们稍后会摆脱这些。先去掉尾递归：

void preorder(Tree t) {
START:
  if (t != null) { 
    list.add(t.val);
    preorder(t.left);
    t = t.right;
    goto START;
  }
}

现在通过在堆栈上保存局部变量（这里只是 t）来“模拟”递归调用，替换参数（这里只是再次 t），然后使用 goto 做同样的事情编译后的代码会用 call/return 指令。

void preorder(Tree t) {
START:
  if (t != null) { 
    list.add(t.val);
    stack.push(t);
    t = t.left; // Simulate the call.
    goto START;
RETURN:         
    t = t.right;
    goto START;
  }
  if (!stack.isEmpty()) { // Simulate the return.
    t = stack.pop();
    goto RETURN;
  }
}

现在我们将转换以摆脱 goto。首先注意goto RETURN可以通过代码motion来消除

void preorder(Tree t) {
START:
  if (t != null) { 
    list.add(t.val);
    stack.push(t);
    t = t.left;
    goto START;    
  }
  if (!stack.isEmpty()) {
    t = stack.pop();
    t = t.right;
    goto START;
  }
}

这只是两个嵌套循环。上面的 if 只是变相的 while 循环：

void preorder(Tree t) {
START:
  while (t != null) { 
    list.add(t.val);
    stack.push(t);
    t = t.left;
  }
  if (!stack.isEmpty()) {
    t = stack.pop();
    t = t.right;
    goto START;
  }
}

剩下的循环运行整个函数体，直到堆栈为空，并在发生这种情况时立即中断：

void preorder(Tree t) {
  for (;;) {
    while (t != null) { 
      list.add(t.val);
      stack.push(t);
      t = t.left;
    }
    if (stack.isEmpty()) break;
    t = stack.pop();
    t = t.right;
  }
}

现在我们可以清理它以实现 Java。

List<Integer> preorder(Tree t) {
  List<Integer> list = new ArrayList<>();
  Deque<Tree> stack = new ArrayDeque<>();
  for (;;) {
    while (t != null) { 
      list.add(t.val);
      stack.push(t);
      t = t.left;
    }
    if (stack.isEmpty()) break;
    t = stack.pop();
    t = t.right;
  }
  return list;
}

这样做的好处是关于堆栈如何工作的零推理。代码上只有代数。稍微练习一下就不难了

它堆叠已经访问过的节点，然后立即向左下降。这意味着堆栈持有等待访问其右子节点的节点，这正是 pop 之后发生的情况。但是，我只是在代码完成后才发现这一点。

无法在 BST 中进行前序遍历

unable to do preorder traversal in BST

java

data-structures

tree

binary-search-tree

tree-traversal