LeetCode 144. Binary Tree Preorder Traversal

原题链接在这里：https://leetcode.com/problems/binary-tree-preorder-traversal/

题目：

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

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

return [1,2,3].

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

题解：

类似Binary Tree Inorder Traversal, Binary Tree Postorder Traversal.

Method 1 是Recursion.

Time Complexity: O(n), 每个点访问了一遍. Space: O(logn), stack space.

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     // Method 1: Recursion
12     public List<Integer> preorderTraversal(TreeNode root) {
13         List<Integer> ls = new ArrayList<Integer>();
14         preorderTraversal(root,ls);
15         return ls;
16         
17     }
18     public void preorderTraversal(TreeNode root, List<Integer> ls) {
19         if(root == null){
20             return;
21         }
22         ls.add(root.val);
23         preorderTraversal(root.left, ls);
24         preorderTraversal(root.right, ls);
25     }
26 }

Method 2 是Iteration，维护一个stack，先压root，stack不空条件下每次循环, 先pop(), 然后压right child, 再压left child. 如此保证了出栈的顺序是preorder.

Time Complexity: O(n). Space: O(logn).

AC Java:

 1 //Method 2: Iteration
 2     public List<Integer> preorderTraversal(TreeNode root) {
 3         List<Integer> ls = new ArrayList<Integer>();
 4         if(root == null){
 5             return ls;
 6         }
 7         Stack<TreeNode> stk = new Stack<TreeNode>();
 8         stk.push(root);
 9         while(!stk.isEmpty()){
10             TreeNode tn = stk.pop();
11             ls.add(tn.val);
12             if(tn.right != null){
13                 stk.push(tn.right);
14             }
15             if(tn.left != null){
16                 stk.push(tn.left);
17             }
18         }
19         return ls;
20     }

Method 3 : 上面的方法是对的，但是为了统一记忆Preorder, Inorder, Postorder, 改写成了下面的Method 3.

进栈的顺序都不变，与Binary Tree Inorder Traversal不同在于加ls的地方不同.

Time Complexity: O(n). Space: O(logn).

AC Java:

 1 //Method 3: Iteration
 2     public List<Integer> preorderTraversal(TreeNode root) {
 3         List<Integer> ls = new ArrayList<Integer>();
 4         Stack<TreeNode> stk = new Stack<TreeNode>();
 5         while(root!=null || !stk.isEmpty()){
 6             if(root != null){
 7                 ls.add(root.val);
 8                 stk.push(root);
 9                 root = root.left;
10             }else{
11                 root = stk.pop();
12                 root = root.right;
13             }
14         }
15         return ls;
16     }

Method 4: Morris Traversal

也是借鉴了Morris Traversal, 与Binary Tree Inorder Traversal相似，唯一不同就是加ls的时机不同。

Time Complexity: O(n). Space: O(1).

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<Integer> preorderTraversal(TreeNode root) {
12         List<Integer> res = new ArrayList<Integer>();
13         TreeNode cur = root;
14         TreeNode pre = null;
15         while(cur != null){
16             if(cur.left == null){
17                 res.add(cur.val);
18                 cur = cur.right;
19             }else{
20                 pre = cur.left;
21                 while(pre.right != null && pre.right != cur){
22                     pre = pre.right;
23                 }
24                 
25                 if(pre.right == null){
26                     res.add(cur.val);
27                     pre.right = cur;
28                     cur = cur.left;
29                 }else{
30                     pre.right = null;
31                     cur = cur.right;
32                 }
33             }
34         }
35         return res;
36     }
37 }

跟上Verify Preorder Sequence in Binary Search Tree, Subtree of Another Tree.