Tree Traversal

pre order

Pre-order: F, B, A, D, C, E, G, I, H.

1. Check if the current node is empty / null
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.

4. Traverse the right subtree by recursively calling the pre-order function.

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> s = new Stack<TreeNode>();
        List<Integer> res = new LinkedList<Integer>();
        if(root!=null) s.push(root);
        while(!s.isEmpty()){
            TreeNode curr = s.pop();
            res.add(curr.val);
            if(curr.right!=null) s.push(curr.right);
            if(curr.left!=null) s.push(curr.left);
        }
        return res;
    }
}

in order

In-order: A, B, C, D, E, F, G, H, I.

1. Check if the current node is empty / null
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).

4. Traverse the right subtree by recursively calling the in-order function.

   In a search tree, in-order traversal retrieves data in sorted order.

   public class Solution {
       public List<Integer> inorderTraversal(TreeNode root) {
           List<Integer> res = new LinkedList<Integer>();
           Stack<TreeNode> s = new Stack<TreeNode>();
           //先将最左边的节点都push进栈
           if(root!=null){
               pushAllTheLeft(s, root);
           }
           while(!s.isEmpty()){
               TreeNode curr = s.pop();
               res.add(curr.val);
               //如果有右子树，将右节点和右子树的最左边的节点都push进栈
               if(curr.right != null){
                   pushAllTheLeft(s, curr.right);
               }
           }
           return res;
       }
   
       private void pushAllTheLeft(Stack<TreeNode> s, TreeNode root){
           s.push(root);
           while(root.left!=null){
               root = root.left;
               s.push(root);
           }
       }
   }

post order

Post-order: A, C, E, D, B, H, I, G, F.

1. Check if the current node is empty / null
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.

4. Display the data part of the root (or current node).

   The trace of a traversal is called a sequentialisation of the tree. The traversal trace is a list of each visited root. No one sequentialisation according to pre-, in- or post-order describes the underlying tree uniquely. Given a tree with distinct elements, either pre-order or post-order paired with in-order is sufficient to describe the tree uniquely. However, pre-order with post-order leaves some ambiguity in the tree structure.

     public class Solution {
       public List<Integer> postorderTraversal(TreeNode root) {
           Stack<PowerNode> s = new Stack<PowerNode>();
           List<Integer> res = new LinkedList<Integer>();
           if(root!=null) s.push(new PowerNode(root, false));
           while(!s.isEmpty()){
               PowerNode curr = s.peek();
               //如果是第二次访问，就计算并pop该节点
               if(curr.visited){
                   res.add(curr.node.val);
                   s.pop();
               } else {
               //如果是第一次访问，就将它的左右节点加入stack，并设置其已经访问了一次
                   if(curr.node.right!=null) s.push(new PowerNode(curr.node.right, false));
                   if(curr.node.left!=null) s.push(new PowerNode(curr.node.left, false));
                   curr.visited = true;
               }
           }
           return res;
       }
   
       private class PowerNode {
           TreeNode node;
           boolean visited;
           public PowerNode(TreeNode n, boolean v){
               this.node = n;
               this.visited = v;
           }
       }
   }

参见wiki

参见[leetcode] Binary Tree Traversal 二叉树遍历