LeetCode | Binary Tree Preorder Traversal

题目

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

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

   1
         2
    /
   3

return [1,2,3].

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

二叉树的先序遍历，递归和非递归两种实现方法。

在非递归实现中，使用栈来保存访问顺序。

代码

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

public class BinaryTreePreorderTraversal {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public ArrayList<Integer> preorderTraversal(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		// recursivePreorderTraversal(root, list);
		iterativePreorderTraversal(root, list);
		return list;
	}

	private void iterativePreorderTraversal(TreeNode root,
			ArrayList<Integer> list) {
		if (root == null) {
			return;
		}

		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			while (node != null) {
				list.add(node.val);
				if (node.right != null) {
					stack.push(node.right);
				}
				node = node.left;
			}
		}
	}

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

LeetCode | Binary Tree Preorder Traversal

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