二叉树的前序中序后序遍历总结

• 用stack的方法分两种，一种直观的dfs像(1)，一种用lastpop(2)或prev(3)记录上一个节点以判断遍历路径。
• 方法(1)的思路是顺着往left走直到遇见NULL，从stack弹出一个往right挪动，继续往left走。
• 方法(2)的思路是，每次循环分push left(left不为NULL并且从上往下遍历)，push right(right不为NULL并且right不是上次遍历的店并且从左边遍历过来或者左边为NULL)，pop(其他情况)三种情况。
• 方法(3)的思路是，每次循环分为from up(如果left不为NULL，push left否则right不为NULL，push right), from left(若right不为空push right),from right(其他情况)三种情况。

1.Discuss区的summary：

1. preorder

   public List<Integer> preorderTraversal(TreeNode root) {
   List<Integer> result = new ArrayList<>();
   Deque<TreeNode> stack = new ArrayDeque<>();
   TreeNode p = root;
   while(!stack.isEmpty() || p != null) {
   if(p != null) {
   stack.push(p);
   result.add(p.val); // Add before going to children
   p = p.left;
   } else {
   TreeNode node = stack.pop();
   p = node.right;
   }
   }
   return result;
   }

2. inorder

   public List<Integer> inorderTraversal(TreeNode root) {
   List<Integer> result = new ArrayList<>();
   Deque<TreeNode> stack = new ArrayDeque<>();
   TreeNode p = root;
   while(!stack.isEmpty() || p != null) {
   if(p != null) {
   stack.push(p);
   p = p.left;
   } else {
   TreeNode node = stack.pop();
   result.add(node.val); // Add after all left children
   p = node.right;
   }
   }
   return result;
   }

3） postorder

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of     preorder
            p = p.right;             // Reverse the process of     preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of     preorder
        }
    }
    return result;
}

//后序遍历的非递归实现
void BT_PostOrderNoRec(pBintree root)
{
    stack<pBintree> s;
    pBintree pre = NULL;
    pBintree top = NULL;
    while((root != NULL) || (!s.empty()))
    {
        if(root != NULL)
        {
            s.push(root);
            root = root->left;
        }
        else
        {
            top = s.top();
            if(top->right != NULL && top->right != pre)
                root = top->right;
            else
            {
                visit(top);
                pre = top;
                s.pop();
            }
        }
    }
}

1. preorder

   void preorder_traversal_iteratively(TreeNode* root)
   {
   if (root == 0)
   return;
   stack<TreeNode> s;
   s.push(root);
   cout << root->val << ' '; // visit root
   TreeNode last_pop = root;
   while (!s.empty())
   {
   TreeNode* top = s.top();
   if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
   {
   s.push(top->left);
   cout << top->left->val << ' '; // visit top->left
   }
   else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
   {
   s.push(top->right);
   cout << top->right->val << ' '; // visit top->right
   }
   else // pop
   {
   s.pop();
   last_pop = top;
   }
   }
   }

2. inorder

   void inorder_traversal_iteratively(TreeNode* root)
   {
   if (root == 0)
   return;
   stack<TreeNode> s;
   s.push(root);
   TreeNode last_pop = root;
   while (!s.empty())
   {
   TreeNode* top = s.top();
   if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
   {
   s.push(top->left);
   }
   else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
   {
   s.push(top->right);
   cout << top->val << ' '; // visit top
   }
   else // pop
   {
   s.pop();
   last_pop = top;
   if (top->right == 0)
   cout << top->val << ' '; // visit top
   }
   }
   }

3. postorder

   void postorder_traversal_iteratively(TreeNode* root)
   {
   if (root == 0)
   return;
   stack<TreeNode> s;
   s.push(root);
   TreeNode last_pop = root;
   while (!s.empty())
   {
   TreeNode* top = s.top();
   if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
   {
   s.push(top->left);
   }
   else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
   {
   s.push(top->right);
   }
   else // pop
   {
   s.pop();
   last_pop = top;
   cout << top->val << ' '; // visit top
   }
   }
   }

//Iterative
public ArrayList<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode prev = null; // previously traversed node
    TreeNode curr = root;

    if (root == null) {
        return result;
    }

    stack.push(root);
    while (!stack.empty()) {
        curr = stack.peek();
        if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree
            if (curr.left != null) {
                stack.push(curr.left);
            } else if (curr.right != null) {
                stack.push(curr.right);
            }
        } else if (curr.left == prev) { // traverse up the tree from the left
            if (curr.right != null) {
                stack.push(curr.right);
            }
        } else { // traverse up the tree from the right
            result.add(curr.val);
            stack.pop();
        }
        prev = curr;
    }

    return result;
}

void postOrder2(TreeNode *root) {
    if(root == NULL)
        return;

    stack<TreeNode *> stk, stk2;
    stk.push(root);
    while(!stk.empty()) {
        TreeNode *pNode = stk.top();
        stk.pop();
        stk2.push(pNode);
        if(pNode->left != NULL)
            stk.push(pNode->left);
        if(pNode->right != NULL)
            stk.push(pNode->right);
    }
    while(!stk2.empty()) {
        cout << stk2.top()->val << endl;
        stk2.pop();
    }
}