LeetCode | Binary Tree Inorder Traversal

题目

Given a binary tree, return the inorder traversal of its nodes‘ values.

For example:
Given binary tree {1,#,2,3},

   1
         2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

老套路，递归（解法1）和非递归（解法2）各来一遍。

解法1

import java.util.ArrayList;

public class BinaryTreeInorderTraversal {
	public ArrayList<Integer> inorderTraversal(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		solve(root, list);
		return list;
	}

	private void solve(TreeNode root, ArrayList<Integer> list) {
		if (root == null) {
			return;
		}
		solve(root.left, list);
		list.add(root.val);
		solve(root.right, list);
	}
}

import java.util.ArrayList;
import java.util.Stack;

public class BinaryTreeInorderTraversal {
	public ArrayList<Integer> inorderTraversal(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while (root != null) {
			stack.push(root);
			root = root.left;
		}
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			list.add(node.val);
			TreeNode right = node.right;
			while (right != null) {
				stack.add(right);
				right = right.left;
			}
		}
		return list;
	}
}

LeetCode | Binary Tree Inorder Traversal,布布扣,bubuko.com

LeetCode | Binary Tree Inorder Traversal

原文：http://blog.csdn.net/perfect8886/article/details/21740797