leetcode经典例题第七题，指定非递归来实现二叉树的前序遍历。

题目描述

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

For example:

Given binary tree{1,#,2,3},

1
2
3
4
5
1
 \
  2
 /
3

return[1,2,3].

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

解题思路

同上题，只需要稍微换一下位置即可，十分方便。

代码提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;
class Command{
    public String str;
    public TreeNode node;
    public Command(String str,TreeNode node){
        this.str = str;
        this.node = node;
    }
}
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go",root));
        while(!stack.isEmpty()){
            Command c = stack.pop();
            if(c.str == "print"){
                res.add(c.node.val);
            }else{
               if(c.node.right != null){
                   stack.push(new Command("go",c.node.right));
               }
               if(c.node.left != null){
                  stack.push(new Command("go",c.node.left));
               }
               stack.push(new Command("print",c.node)); 
            }
        }
        return res;
    }
}