In sum for pre- / In- and Post- order Traversal

来源:转载

Preorder binary tree traversal is a classic interview problem about trees. The key to solve this problem is to understand the following:

  1. What is preorder? (parent node is processed before its children)
  2. Use Stack from Java Core library

It is not obvious what preorder for some strange cases. However, if you draw a stack and manually execute the program, how each element is pushed and popped is obvious.

The key to solve this problem is using a stack to store left and right children, and push right child first so that it is processed after the left child.

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }} public class Solution { public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> returnList = new ArrayList<Integer>(); if(root == null) return returnList; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while(!stack.empty()){ TreeNode n = stack.pop(); returnList.add(n.val); if(n.right != null){ stack.push(n.right); } if(n.left != null){ stack.push(n.left); } } return returnList; }}

The key to solve inorder traversal of binary tree includes the following:

  1. The order of "inorder" is: left child -> parent -> right child
  2. Use a stack to track nodes
  3. Understand when to push node into the stack and when to pop node out of the stack
//Definition for binary treepublic class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public ArrayList<Integer> inorderTraversal(TreeNode root) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. ArrayList<Integer> lst = new ArrayList<Integer>(); if(root == null) return lst; Stack<TreeNode> stack = new Stack<TreeNode>(); //define a pointer to track nodes TreeNode p = root; while(!stack.empty() || p != null){ // if it is not null, push to stack //and go down the tree to left if(p != null){ stack.push(p); p = p.left; // if no left child // pop stack, process the node // then let p point to the right }else{ TreeNode t = stack.pop(); lst.add(t.val); p = t.right; } } return lst; }}

Java Solution 2 - Recursive

The recursive solution is trivial.

public class Solution { List<Integer> result = new ArrayList<Integer>(); public List<Integer> inorderTraversal(TreeNode root) { if(root !=null){ helper(root); } return result; } public void helper(TreeNode p){ if(p.left!=null) helper(p.left); result.add(p.val); if(p.right!=null) helper(p.right); }}

Among preoder, inorder and postorder binary tree traversal problems, postorder traversal is the most complicated one.

Analysis

The key to to iterative postorder traversal is the following:

  1. The order of "Postorder" is: left child -> right child -> parent node.
  2. Find the relation between the previously visited node and the current node
  3. Use a stack to track nodes

As we go down the tree to the lft, check the previously visited node. If the current node is the left or right child of the previous node, then keep going down the tree, and add left/right node to stack when applicable. When there is no children for current node, i.e., the current node is a leaf, pop it from the stack. Then the previous node become to be under the current node for next loop. You can using an example to walk through the code.

For example, for the following tree, the post order traversal returns {4, 6, 5, 2, 3, 1}.

//Definition for binary treepublic class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }} public class Solution { public ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> lst = new ArrayList<Integer>(); if(root == null) return lst; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); TreeNode prev = null; while(!stack.empty()){ TreeNode curr = stack.peek(); // go down the tree. //check if current node is leaf, if so, process it and pop stack, //otherwise, keep going down if(prev == null || prev.left == curr || prev.right == curr){ //prev == null is the situation for the root node if(curr.left != null){ stack.push(curr.left); }else if(curr.right != null){ stack.push(curr.right); }else{ stack.pop(); lst.add(curr.val); } //go up the tree from left node //need to check if there is a right child //if yes, push it to stack //otherwise, process parent and pop stack }else if(curr.left == prev){ if(curr.right != null){ stack.push(curr.right); }else{ stack.pop(); lst.add(curr.val); } //go up the tree from right node //after coming back from right node, process parent node and pop stack. }else if(curr.right == prev){ stack.pop(); lst.add(curr.val); } prev = curr; } return lst; }}




分享给朋友:
您可能感兴趣的文章:
随机阅读: