Tree Traversal

pre order

pre-order.png

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.png

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.png

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 二叉树遍历