Construct Binary Tree from Preorder and Inorder Traversal, Construct Binary Tree from Inorder and Postorder Traversal, Binary Tree Inorder Traversal, Convert Sorted Array to Binary Search Tree, Convert Sorted List to Binary Search Tree, Flatten Binary Tree to Linked List

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

Solution

int pre=0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
    //if(preorder.length==0||inorder.length==0){return null;}
    int l=0;
    int r=preorder.length-1;
    return build(preorder,inorder,l, r);
}
public TreeNode build(int[] preorder, int[] inorder,int l, int r){
    if(l>r){return null;}
    int cur=preorder[pre];
    TreeNode node=new TreeNode(cur);
    pre++;
    int i=0;
    for (i=l; i<=r; i++){
        if(inorder[i]==cur)
        {break;}
    }
     
    node.left=build(preorder,inorder,l, i-1);
    node.right=build(preorder,inorder,i+1, r);
    
   return node;
}

---

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

Almost the same with previous one, only this time we scan postorder from backwards and recursively add to the right subtree first.

int pos=0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        pos=inorder.length-1;
       return helper(inorder, postorder, 0, inorder.length-1);
    }
    
    private TreeNode helper(int[] inorder, int[] postorder, int l, int r){
            if(l>r) return null;
            int cur=postorder[pos];
            TreeNode tmp=new TreeNode(cur);
            pos--;
            int i=l;
            for(;i<=r;i++){
                if(inorder[i]==cur) break;
            }
            
            tmp.right=helper(inorder,postorder, i+1, r);
            tmp.left=helper(inorder, postorder, l, i-1);
            return tmp;
    }

---

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},

1
 \
  2
 /
3

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

Recursive Method(Trivial)

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> res= new ArrayList<Integer>();
      //第一次没过..少了这句
      if(root==null) return res;
    return helper(root,res);
}
private  ArrayList<Integer> helper(TreeNode cur,ArrayList<Integer> res){
    if(cur==null) return null;
    helper(cur.left, res);
    res.add(cur.val);
    helper(cur.right, res);
    return res;
}

Iterative Method

Inorder: left child -> parent -> right child

Use a stack to track nodes

Exit while loop when stack is empty and current node is null

push nodes in the stack when current node is not null, then move to left subtree
pop node when current node is null, move to right subtree

public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res= new ArrayList<Integer>();
        Stack<TreeNode> nodestack=new Stack<TreeNode>();
        if(root==null) return res;
        while(!nodestack.isEmpty() || root!=null){
            if(root!=null){
                nodestack.push(root);
                root=root.left;
            }
            else{
                TreeNode tmp=nodestack.pop();
                res.add(tmp.val);
                root=tmp.right;
            }
        }
        return res;
}

---

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Solution

Use recursion, find median element each time, move to left/right subtree.

public TreeNode sortedArrayToBST(int[] num) {
       return helper(num, 0, num.length-1);
   }
   
   private TreeNode helper(int[] num,int l, int r){
       if(l>r) return null;
       int mid=(l+r)/2;
       TreeNode newnode=new TreeNode(num[mid]);
       newnode.left=helper(num, l, mid-1);
       newnode.right=helper(num, mid+1, r);
       return newnode;
   }

---

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Naive Solution

Just convert LinkedList to Array first…

public TreeNode sortedListToBST(ListNode head) {
       ListNode cur = head;
       List<Integer> res = new ArrayList<Integer>();
       while (cur != null) {
           res.add(cur.val);
           cur = cur.next;
       }
       return helper(res, 0, res.size() - 1);
   }
    private TreeNode helper(List<Integer> res,int l, int r){
       if(l>r) return null;
       int mid=(l+r)/2;
       TreeNode newnode=new TreeNode(res.get(mid));
       newnode.left=helper(res, l, mid-1);
       newnode.right=helper(res, mid+1, r);
       return newnode;
   }

Recursive Solution

The trick here is to use two pointers, one slow and one twice the speed, to find the median element.

public static TreeNode sortedListToBST(ListNode head) {  
        return rec(head, null);  
    }  
      
    // 在区间[start, end)里递归，后面的end是包括在内的，这样可以避免要多用一个指针来记录mid前的节点  
    public static TreeNode rec(ListNode start, ListNode end){  
        if(start == end){  
            return null;  
        }  
          
        // 一次遍历找到中点的方法：快慢指针  
        ListNode mid = start;           // 该指针最终会指向中点  
        ListNode probe = start;         // 探针最终会到达end  
        while(probe!=end && probe.next!=end){       // 探针完成搜索，注意停止条件是和end比较而不是和null比！  
            mid = mid.next;  
            probe = probe.next.next;  
        }  
          
        TreeNode root = new TreeNode(mid.val);  
        root.left = rec(start, mid);  
        root.right = rec(mid.next, end);  
        return root;  
    }

---

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.
For example,
Given

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Iterative Solution

Using a stack to solve this problem is easy: start from root, push right, left into stack. If stack is not empty, set cur.right to stack.peek(). Continue to process the next node from top of stack.
But to do it inplace requires to keep track of the origin right node. Overall process is to squeeze the left node into between its parents and right child.

public void flatten(TreeNode root) {
        TreeNode head=new TreeNode(0);
        head.right=root;
        TreeNode cur=head;
        
        while(cur.right!=null){
            cur=cur.right;
            if(cur.left!=null){
                TreeNode end=cur.left;
                while(end.right!=null)
                end=end.right;
                TreeNode tmp=tmp=cur.right;
                cur.right=cur.left;
                end.right=tmp;
                cur.left=null;
            }
        } head.right=null;
        
    }