二叉树中非递归的前序排列怎么理解

Question

非递归前序排列代码/** Inorder traversal from the root*/
    public void nonRecursivePreorder() {
      java.util.ArrayList list = new java.util.ArrayList();
      MyStack stack = new MyStack();      if (root == null) return;      stack.push(root);      while (!stack.isEmpty()) {  //这段无法理解
        TreeNode node = (TreeNode)(stack.peek());
        stack.pop(); // Remove the node from the stack
        list.add(node);
        
        if (node.right != null && !list.contains(node.right)) {  // 为什么这么写
          stack.push(node.right); // Add the right node to the stack
        }
        
        if (node.left != null && !list.contains(node.left)) {
          stack.push(node.left); // Add the left node to the stack
        }
      }      for (int i = 0; i < list.size(); i++)
        System.out.print(((TreeNode)(list.get(i))).element + " ");
    }递归的代码 private void preorder(TreeNode root) {
      if (root == null) {
        return;
      }
      System.out.print(root.element + " ");
      preorder(root.left);
      preorder(root.right);
    }求指导，栈的操作过程是怎么样的

Answer 1

/** Inorder traversal from the root*/
    public void nonRecursivePreorder() {
      java.util.ArrayList list = new java.util.ArrayList();
      MyStack stack = new MyStack();      if (root == null) return;      stack.push(root);      while (!stack.isEmpty()) {  
        //因为先序是根左右，所以不为空则弹出根节点
        TreeNode node = (TreeNode)(stack.peek());
        stack.pop(); // Remove the node from the stack
        list.add(node);
        
        if (node.right != null && !list.contains(node.right)) {  
          stack.push(node.right); // 有右节点则将右节点压栈
        }
        
        if (node.left != null && !list.contains(node.left)) {
          stack.push(node.left); // 有左节点则将左节点压栈，因为栈是后进先出，所以这个左子节点会
                                 //在下一次循环当做根节点出栈
        }
      }//也许是我语言匮乏，不知道该怎么解释了，这段程序基本很难再清晰了      for (int i = 0; i < list.size(); i++)
        System.out.print(((TreeNode)(list.get(i))).element + " ");
    }