Binary Tree Inorder Traversal

Leave a comment

November 6, 2016 by oneOokay

Non-recursive:

一个while loop搞定:得背下来吧。

 public List inorderTraversal(TreeNode root) {
 List ans = new ArrayList();
 if (root == null){
 return ans;
 }
 Stack stack = new Stack();
 while (root != null || !stack.isEmpty()){
 while (root != null){
 stack.push(root);
 root = root.left;
 }
 root = stack.pop(); //直接把stack.pop()出来的值赋给root,省去了一个变量
 ans.add(root.val);
 root = root.right;
 }
 
 return ans;
 }

Recursive: Divide & conquer:

list.addAll()

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null){
            return ans;
        }        
        ans.addAll(inorderTraversal(root.left));
        ans.add(root.val);
        ans.addAll(inorderTraversal(root.right));        
        return ans;
    }

//如果不会list.addAll()的话,就用一个helper函数
public List<Integer> inorderTraversal(TreeNode root) {
 List<Integer> ans = new ArrayList<>();
 helper(root, ans);
 return ans;
 }
 
 public void helper(TreeNode node, List<Integer> list){
 if (node == null) return;
 helper(node.left, list);
 list.add(node.val);
 helper(node.right, list);
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: