Binary Tree Traversal 3 种

百度这张图说明了所有问题，前序遍历得到的结果，root 在最前方。

后序遍历得到的结果，root在最后。

中序遍历得到的结果，root 在中央。

所以leetcode上有关traversal的题目，给定preorder 和 inorder 的结果，tree可还原。

给定postorder和inorder的结果，tree可还原。

关于遍历的代码：

rec写法很简单：

private ArrayList<Integer> result = new ArrayList<Integer>();
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        if(root!=null){
        	inorderTraversal(root.left);
        	result.add(root.val);
        	inorderTraversal(root.right);
        }
        return result;
    }

public ArrayList<Integer> preorderTraversal(TreeNode root) {
        if(root!=null){
        	result.add(root.val);
        	preorderTraversal(root.left);
        	preorderTraversal(root.right);
        }
        return result;
    }

public ArrayList<Integer> postorderTraversal(TreeNode root) {
		if (root != null) {
			postorderTraversal(root.left);
			postorderTraversal(root.right);
			result.add(root.val);
		}
		return result;
	}

如果要用iterate, 那就稍微麻烦，用stack做。

public ArrayList<Integer> inorderTraversal(TreeNode root){
		ArrayList<Integer> result = new ArrayList<Integer>();
		TreeNode p = root;
		Stack<TreeNode> st = new Stack<TreeNode>();
		while(!st.isEmpty()||p!=null){
			if(p!=null){
				st.push(p);
				p = p.left;
			}else{
				p = st.pop();
				result.add(p.val);
				p = p.right;
			}
		}
		return result;
	}

public ArrayList<Integer> preorderTraversal2(TreeNode root){
		ArrayList<Integer> result = new ArrayList<Integer>();
		TreeNode p = root;
		Stack<TreeNode> st = new Stack<TreeNode>();
		if(p!=null)
			st.push(p);
		while(!st.isEmpty()){
			p = st.pop();
			result.add(p.val);
			if(p.right!=null) 
				st.push(p.right);
			if(p.left!=null)
				st.push(p.left);
		}
		return result;
	}

public ArrayList<Integer> postorderTraversal2(TreeNode root){
		ArrayList<Integer> result = new ArrayList<Integer>();
		TreeNode cur, pre;
		Stack<TreeNode> st = new Stack<TreeNode>();
		cur = root;
		do{
			while(cur!=null){
				st.push(cur);
				cur = cur.left;
			}
			pre = null;
			while(!st.isEmpty()){
				cur = st.pop();
				if(cur.right==pre){
					result.add(cur.val);
					pre = cur;
				}else{
					st.push(cur);
					cur = cur.right;
					break;
				}
			}
		}while(!st.isEmpty());
		return result;
	}

Binary Tree Traversal 3 种

原文：http://blog.csdn.net/yiding_he/article/details/19146167