Flatten Binary Tree to Linked List – leetcode

Question:
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

Thought:
The order after flatten is pre order traverse, so for each right node, we find its pre-node in pre-order traverse. If we find one, attach them and swap left and right, make left=null.

If we don’t find one, that means current node’s left==null, cur=cur.right;

Note: don’t forget to make left=null after swap.

Code:

    public void flatten(TreeNode root) {
        TreeNode cur=root;
        while(cur!=null){
            TreeNode right=cur.right;
            TreeNode left=cur.left;
            TreeNode run=left;
            while(run!=null&&run.right!=null){
                run=run.right;
            }
            if(run!=null){
                run.right=right;
                cur.right=left;//bug if(run==null), we should not do this operation..
                cur.left=null;//bug
            }
            cur=cur.right;
        }
    }

Path Sum II – leetcode

Question:
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]

Thought:
Standard DFS. Use a list to track current path. If requirement is met, we add to result list.

Code:

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
         List<List<Integer>> result= new ArrayList<>();
         if(root==null) return result;
         pathSum(root,sum,new ArrayList<Integer>(),result);
        return result;
    }
    public void pathSum(TreeNode root,int sum,List<Integer> path,List<List<Integer>> result){
         List<Integer> aPath= new ArrayList<>(path);
         aPath.add(root.val);
         int newSum=sum-root.val;
         if(root.left==null&&root.right==null&&newSum==0){
                 result.add(aPath);
                 return;
         }
         if(root.left!=null){
           pathSum(root.left,newSum,aPath,result);
         }
         if(root.right!=null){
            pathSum(root.right,newSum,aPath,result); 
         }
    }

Path Sum – leetcode

Question:
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Thought:
DFS, if we reached leaf and the new sum is 0, then return true;

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {//bug note if root==null, even sum=0 should return false;
            return false;
        }
        int val = sum - root.val;
        if (val == 0 && root.left == null && root.right == null)
            return true;
        else {
            return hasPathSum (root.left, val) || hasPathSum (root.right, val);
        }
    }
    
    

Minimum Depth of Binary Tree – leetcode

Question:
Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Thought:

DFS, one thing need notice, if one of minLeft and minRight is 0, we should calculate based on the non-0 one. Take below as example: when we at 2, left is 1, right 0, right doesn’t count, so only left count as leaf.

1
2 3
4

    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        int minLeft=minDepth(root.left);
        int minRight=minDepth(root.right);
        if(minLeft==0||minRight==0){  //bug
            return minLeft>=minRight?minLeft+1:minRight+1;
        }
        return Math.min(minLeft,minRight)+1;
    }

BFS. level by level traverse, if we met a leaf, we stop and return level count.

    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        Queue <TreeNode> h = new LinkedList <TreeNode> ();
        h.add (root);
        Queue <TreeNode> newh = new LinkedList <TreeNode> ();
        int count = 0;
        while (!h.isEmpty ()) {
            TreeNode t = h.remove ();
            if (t.left == null && t.right == null) {
                break;
            } else {
                if (t.left != null) {
                    newh.add (t.left);
                } 
                if(t.right != null) {
                    newh.add (t.right);
                }
            }
            if (h.isEmpty ()) {
                h = newh;
                newh = new LinkedList <TreeNode> ();
                count++;
            }
        }
        return count + 1;
    }

Things that need revisit

Convert Sorted List to Binary Search Tree

Populating Next Right Pointers in Each Node II

Binary Tree Maximum Path Sum

Word Ladder II

Max Points on a Line

Convert Sorted Array to Binary Search Tree – leetcode

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

Thought:
Since it is a sorted array, the mid element is our root, we use dfs to get the left and right node.

Code:

    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums==null) return null;
        return dfs(nums,0,nums.length-1);
    }
    
    public TreeNode dfs(int[] nums, int start, int end){
        if(start>end) return null;
        int mid=start+(end-start)/2;
        TreeNode node= new TreeNode(nums[mid]);
        node.left=dfs(nums,start,mid-1);
        node.right=dfs(nums,mid+1,end);
        return node;
    }

Balanced Binary Tree – leetcode

Question:
Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Thought:
We need to get the depth of left subtree and right subtree. If their height difference is bigger than 1, return false. Along the way,we can do check to see if any of the layer we found height difference is larger than 1, we can say it is not balanced.

    public boolean isBalanced(TreeNode root) {
        return getDepth(root)!=-1;
    }
    public int getDepth(TreeNode root){
        if(root==null) return 0;
        int left=getDepth(root.left);
        int right=getDepth(root.right);
        if(left==-1||right==-1) return -1;//bug
        if(Math.abs(left-right)>1) 
        return -1;
        else return Math.max(left,right)+1;
    }
    
    

Construct Binary Tree from Inorder and Postorder Traversal – leetcode

Question:
Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Thought:
For post order, visit order is left node, right node then node itself. Hence the last element in the postorder array is root. Again, we use index of root to locate how many nodes are in left and how many nodes are in right. Then recursively get its left child and right child.

Code:

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder==null||postorder==null) return null;
        return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }

    public TreeNode buildTree(int[] inorder, int is, int ie, int[] postorder, int ps, int pe){
        if(is>ie||ps>pe) return null;
        TreeNode node=new TreeNode(postorder[pe]);
        int index=0;
        for(int i=is;i<=ie;i++){
            if(inorder[i]==node.val){
                index=i;
                break;
            }
        }
        int leftNum=index-is;
        int rightNum=ie-index;
        node.left=buildTree(inorder,is,index-1,postorder,ps,ps+leftNum-1); //bug
        node.right=buildTree(inorder,index+1,ie,postorder,pe-rightNum,pe-1); //bug
        return node;
    }
    

Construct Binary Tree from Preorder and Inorder Traversal – leetcode

Question:
Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Thought:
DFS.
Preorder array, the root node will the the first element. We locate the index for the first element in the inorder array, all the element in the left in inorder array is root node’s left child. the other half is right child.
We use dfs to get left child and right child, return the root.

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||inorder==null) return null;
        return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    
    public TreeNode buildTree(int[] preorder, int ps, int pe, int[] inorder, int is,int ie){
        if(ps>pe||is>ie) return null;
        TreeNode n= new TreeNode(preorder[ps]);
        int index=0;
        for(int i=is;i<=ie;i++){
            if(inorder[i]==n.val){
                index=i;
            }
        }
        int leftNum=index-is;
        int rightNum=ie-index;
        n.left=buildTree(preorder,ps+1,ps+leftNum,inorder,is,index-1);
        n.right=buildTree(preorder,pe-rightNum+1,pe,inorder,index+1,ie);
        return n;
        
    }
    

Binary Tree Zigzag Level Order Traversal – leetcode

Question:
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

Thought:
We can use stack to store the element so next level will be in reverse order. Use a boolean to see the order to add to the stack. See code blow for this solution.

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Stack<TreeNode> s1= new Stack<>();
        Stack<TreeNode> s2= new Stack<>();
        boolean flip=true;
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> aList= new ArrayList<>();
        if(root!=null )s1.push(root);
        while(!s1.isEmpty()){
            TreeNode cur= s1.pop();
            aList.add(cur.val);
            if(flip){
                if(cur.left!=null) s2.push(cur.left);
                if(cur.right!=null) s2.push(cur.right);
            }else{
                if(cur.right!=null) s2.push(cur.right);
                 if(cur.left!=null) s2.push(cur.left);
            }
            if(s1.isEmpty()){
                s1=s2;
                s2=new Stack<>();
                result.add(aList);
                aList= new ArrayList<>();
                flip=!flip;
            }
        }
        return result;
    }

Another solution, we can use a queue, same as level order traverse. And a flag, keep track of the order we insert to List, if true, always insert to head, if false, always insert to tail.