Twenty Percent Knowledge: tree

Saturday, June 11, 2016

Path Sum II

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]
]

One submission to pass. Yaay!

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        List<Integer> path = new LinkedList<Integer>();
        dfs(root,result,path,0,sum);
        return result;
    }
    void dfs(TreeNode root,List<List<Integer>> result, List<Integer> path,int curSum,int sum){
        if(root==null)return;
        curSum+=root.val;
        path.add(root.val);
        //at leaf node, decide if new list should be created according to sum matching
        if(root.left==null&&root.right==null&&curSum==sum){
            LinkedList<Integer> aList= new LinkedList<Integer>();
            aList.addAll(path);
            result.add(aList);
            path.clear();
            return;
        }
       
        //left
        List<Integer> newList = new LinkedList<Integer>();
        newList.addAll(path);//use a different list to reserve same path for right
        dfs(root.left,result,newList,curSum,sum);
        newList.clear();
        newList.addAll(path);
        dfs(root.right,result,newList,curSum,sum);
    }
}

Sunday, July 12, 2015

Build Binary Tree from Array Traversal Result

From a tree, you can traversal it with preorder, inorder and post order (DFT) or level by level. You can not restore a tree from only one of result without extra information, but you have chance to restore it with two types of result.

For example, most common one is to restore a binary tree from preorder and inorder results.

In preorder, first element is the root, then entire left tree and then entire right tree.
In inorder, root is somewhere in the middle, left to it is entire left tree, right to it is entire right tree. you can use root from preorder to locate its position in an inorder array.

And with root position in in-order array, number of elements in left tree can be figured out, with this information, boundary of preorder's left and right subtrees can be extracted out.

Since each node is also a tree, then recursively applying this algorithm, it will be able to find children for all parents.

Preorder and post order won't work, because it can not find out root.

public static TreeNode rebuildBinaryTreeRec(List<Integer> preOrder, List<Integer> inOrder){  
        TreeNode root = null;  
        List<Integer> leftPreOrder;  
        List<Integer> rightPreOrder;  
        List<Integer> leftInorder;  
        List<Integer> rightInorder;  
        int inorderPos;  
        int preorderPos;  
   
        if ((preOrder.size() != 0) && (inOrder.size() != 0))  
        {  
            // first element in preorder array is root  
            root = new TreeNode(preOrder.get(0));  
   
            //  Based upon the root information, manupulate preorder array to separate it into left and right subarrays
   // find root according to root in preorder
            inorderPos = inOrder.indexOf(preOrder.get(0));      
            leftInorder = inOrder.subList(0, inorderPos);  
            rightInorder = inOrder.subList(inorderPos + 1, inOrder.size());  
   //then according to in order sub tree information, help preorder to determine the left and right tree
            preorderPos = leftInorder.size();
            leftPreOrder = preOrder.subList(1, preorderPos + 1);  
            rightPreOrder = preOrder.subList(preorderPos + 1, preOrder.size());  
   //then root's left subtree is the subtree built from left preorder and left inorder subtrees
            root.left = rebuildBinaryTreeRec(leftPreOrder, leftInorder); 
   //root's right tree is the tree built from right part of preorder subtree and right part of in order subtree
            root.right = rebuildBinaryTreeRec(rightPreOrder, rightInorder);   
        }  
  //return the root of subtrees
        return root;  
    }