LeetCode 144. Binary Tree Preorder Traversal 解題報告

144. Binary Tree Preorder Traversal

My SubmissionsQuestionTotal Accepted:108336Total Submissions:278322Difficulty:Medium

Given a binary tree, return thepreordertraversal 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?

Subscribeto see which companies asked this question

Show Tags Show Similar Problems Have you met this question in a real interview? Yes No  

求一棵二叉樹的先根遍歷序。題目說了，遞歸的解法十分簡單，能否用非遞歸的方式求解。

每遍歷一個節點的時候，將右孩子入棧。向左搜索直到為空時，彈棧。

我的AC代碼

public class BinaryTreePreorderTraversal {
	
	public List preorderTraversal(TreeNode root) {
        List list = new ArrayList();
        Stack stack = new Stack();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				list.add(cur.val);
				if(cur.right != null) stack.add(cur.right);
				cur = cur.left;
			}
			if(!stack.isEmpty()) cur = stack.pop();
		}
        return list;
    }
}