LeetCode 第144题 二叉数的前序遍历

 1 class Solution144 {
 2 
 3   List<Integer> res = new ArrayList<>();
 4 
 5   //递归
 6   public List<Integer> preorderTraversal(TreeNode root) {
 7     search(root);
 8     return res;
 9   }
10 
11   void search(TreeNode root) {
12     if (root != null) {
13       res.add(root.val);
14       search(root.left);
15       search(root.right);
16     }
17   }
18 
19   //非递归
20   public List<Integer> preorderTraversal_2(TreeNode root) {
21     Stack<TreeNode> stack = new Stack<>();
22     TreeNode currNode = root;
23     while (currNode != null || !stack.isEmpty()) {
24       while (currNode != null) {
25         res.add(currNode.val);
26         stack.push(currNode);
27         currNode = currNode.left;
28       }
29 
30       currNode = stack.pop();
31       currNode = currNode.right;
32     }
33 
34     return res;
35   }
36 }