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?
题目大意：非递归方式实现二叉树的前序遍历。
解题思路：自己实现一个栈，循环（根节点直接入栈并且入res List，循环入栈左子树，pop栈，入栈右子树）。
public class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while(curr!=null||!stack.isEmpty()){ while(curr!=null){ stack.push(curr); res.add(curr.val); curr=curr.left; } curr = stack.pop(); curr = curr.right; } return res; } }
Binary Tree Preorder Traversal —— LeetCode
原文：http://www.cnblogs.com/aboutblank/p/4526386.html