Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example

Given the below binary tree:

  1
 / \
2   3

return 6.

Solution: Divide and Conquer. for each node, calculate two maxPath:

1. maxSinglePath: start from root to any nodes, could be empty. 从root往下走到任意点的最大路径,这条路径可以不包含任何点.

2. maxPath: 从树中任意到任意点的最大路径,这条路径至少包含一个点. Max path in the tree, can not be empty, doesn’t have to include root.

So the result is root.maxPath

O(n) time complexity. Each node is visited once.

Version 1. cleaner version, with global variable

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
     
    int maxPath = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        maxSinglePath(root);
        return maxPath;
    }
    
    public int maxSinglePath(TreeNode root){
        if(root==null){
            return 0;
        }
        //devide
        int left = Math.max(0, maxSinglePath(root.left));
        int right = Math.max(0, maxSinglePath(root.right));
        
        //conquer
        maxPath = Math.max(maxPath, left+right+root.val);
        
        return Math.max(left, right)+root.val;
    }
}

Version 2. jiuzhang, with result class

private class maxPathResult {
    int maxSinglePath;
    int maxPath;
    public maxPathResult(int maxSinglePath, int maxPath) {
        this.maxSinglePath = maxSinglePath;//start from root to any nodes, could be empty
        this.maxPath = maxPath;//max path in the tree, can not be empty, doesn't have to include root
    }
}
public int maxPathSum(TreeNode root) {
    // write your code here
    return helper(root).maxPath;
}

public maxPathResult helper(TreeNode root) {
    if (root == null) {
        return new maxPathResult(0, Integer.MIN_VALUE);
    }
    //devide
    maxPathResult left = helper(root.left);
    maxPathResult right = helper(root.right);

    //conquer
    int maxSinglePath = Math.max(left.maxSinglePath, right.maxSinglePath) + root.val;
    maxSinglePath = Math.max(maxSinglePath, 0);

    int maxDoublePath = left.maxSinglePath + right.maxSinglePath + root.val;

    int maxPath = Math.max(Math.max(left.maxPath, right.maxPath), maxDoublePath);
    return new maxPathResult(maxSinglePath, maxPath);
}

 

FacebookTwitterGoogle+Share

Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal

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

Solution: Use two linked list to represent curr level and the next level. While iterating through the node on the current level, we put the child nodes to next level in order based on if the current level is odd or even.

If current is odd level, so next level should be right->left, so we always insert right node in front of left node.

If current is even level, so next level should be left->right, we always insert left node in front of right node.

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> curr = new LinkedList<>();
        LinkedList<TreeNode> next = new LinkedList<>();
        curr.add(root);
        while (!curr.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            while (!curr.isEmpty()) {
                TreeNode node = curr.remove();
                tmp.add(node.val);
                //current is odd level
                //so next level should be right->left
                if (res.size() % 2 == 0) {
                    if (node.left != null) {
                        next.add(0, node.left);
                    }
                    if (node.right != null) {
                        next.add(0, node.right);
                    }
                }
                //current is even level
                //so next level should be left->right
                else {
                    if (node.right != null) {
                        next.add(0, node.right);
                    }
                    if (node.left != null) {
                        next.add(0, node.left);
                    }
                }
            }
            curr = next;
            next = new LinkedList<>();
            res.add(tmp);
        }
        return res;
    }

Count Univalue Subtrees

Count Univalue Subtrees

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

return 4.

Solution:

public int countUnivalSubtrees(TreeNode root) {
    int[] count = new int[1];
    isUnivalSubtrees(root, count);
    return count[0];
}

public boolean isUnivalSubtrees(TreeNode root, int[] count) {
    if (root == null) {
        return false;
    }
    boolean left = isUnivalSubtrees(root.left, count);
    boolean right = isUnivalSubtrees(root.right, count);
    if (!left && !right) {
        if (root.left == null && root.right == null) {
            count[0]++;
            return true;
        }
    } else if (left && right) {
        if (root.left.val == root.val && root.right.val == root.val) {
            count[0]++;
            return true;
        }
    } else if (left && !right) {
        if (root.right == null && root.left.val == root.val) {
            count[0]++;
            return true;
        }
    } else if (!left && right) {
        if (root.left == null && root.right.val == root.val) {
            count[0]++;
            return true;
        }
    }
    return false;
}

Count of Smaller Number I && II

Count of Smaller Number I 

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller that the given integer.

Example

For array [1,2,7,8,5], and queries [1,8,5], return [0,4,2]

Note

We suggest you finish problem Segment Tree Build and Segment Tree Query II first.

Challenge

Could you use three ways to do it.

  1. Just loop
  2. Sort and binary search
  3. Build Segment Tree and Search.

Solution:  Version 1. sort + binary search O(nlogn) Time
//Version 2. Segment Tree. not as efficient as version 1.
//check <Count of Smaller Number II>

public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
    //Version 1. sort + binary search
    //Version 2. Segment Tree. not as efficient as version 1.
    //check <Count of Smaller Number before itself>
    ArrayList<Integer> result = new ArrayList<>();
    if (A == null || queries == null) {
        return result;
    }
    if (A.length == 0) {
        for (int i = 0; i < queries.length; i++) {
            result.add(0);
        }
        return result;
    }
    Arrays.sort(A);
    for (int i = 0; i < queries.length; i++) {
        int target = queries[i];
        //find the last element A[i]<target, i+1 is the number
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[end] < target) {
            result.add(end + 1);
        } else if (A[start] < target) {
            result.add(start + 1);
        } else {
            result.add(0);
        }
    }
    return result;
}

Count of Smaller Number II

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) . For each elementAi in the array, count the number of element before this element Ai is smaller than it and return count number array.

Example

For array [1,2,7,8,5], return [0,1,2,3,2]

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number before itself I first.

Solution: Segment Tree. 这道题不能用sort+binary search的方法了因为顺序不能改变。

建一个0-10000的值型线段树。然后每个叶子节点代表这个值的count。所以在A[i]之前比它小的数的个数就是那个0~A[i]-1这个node 的count值。之后每次Query以后把A[i]那个leaf node count++, 相应回溯更新它所有父亲节点。

时间复杂度是O(m + nlogm) m是值的区间,n是query个数。

这个算法是否最优需要分情况,如果值特别分散且query数特别小,那还不如每次query用O(n)的时间count它之前的比她小的数。

public class SegmentTreeNode {
    int start, end;
    int count;
    SegmentTreeNode left;
    SegmentTreeNode right;
    public SegmentTreeNode(int start, int end) {
        this.start = start;
        this.end = end;
        this.count = 0;
    }
}

public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
    ArrayList<Integer> result = new ArrayList<>();
    if (A == null || A.length == 0) {
        return result;
    }
    SegmentTreeNode node = buildSegmentTree(0, 10000);
    for (int i = 0; i < A.length; i++) {
        if (A[i] == 0) {
            result.add(0);
        } else {
            result.add(query(node, 0, A[i] - 1));
        }
        update(node, A[i]);
    }
    return result;
}

public SegmentTreeNode buildSegmentTree(int start, int end) {
    SegmentTreeNode node = new SegmentTreeNode(start, end);
    if (start < end) {
        int mid = start + (end - start) / 2;
        node.left = buildSegmentTree(start, mid);
        node.right = buildSegmentTree(mid + 1, end);
        node.count = node.left.count + node.right.count;
    }
    return node;
}

public int query(SegmentTreeNode node, int start, int end) {
    if (node.start == start && node.end == end) {
        return node.count;
    }
    int leftCount = 0, rightCount = 0;
    int mid = node.start + (node.end - node.start) / 2;
    if (start <= mid) {
        if (end <= mid) {
            leftCount = query(node.left, start, end);
        } else {
            leftCount = query(node.left, start, mid);
        }
    }
    if (end > mid) {
        if (start > mid) {
            rightCount = query(node.right, start, end);
        } else {
            rightCount = query(node.right, mid + 1, end);
        }
    }
    return leftCount + rightCount;
}

public void update(SegmentTreeNode node, int index) {
    if (node.start == index && node.end == index) {
        node.count = node.count + 1;
    } else {
        int mid = node.start + (node.end - node.start) / 2;
        if (node.start <= index && index <= mid) {
            update(node.left, index);
        } else if (mid < index && index <= node.end) {
            update(node.right, index);
        }
        node.count = node.left.count + node.right.count; //or node.count = node.count+1;
    }
}

Interval Sum I && II

Interval Sum I

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the sum number between index start and end in the given array, return the result list.

Example

For array [1,2,7,8,5], and queries [(0,4),(1,2),(2,4)], return [23,9,20]

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge

O(logN) time for each query

Solution: Version 1. prefix sum,
(Version 2. Segment tree: check Interval Sum II)

public ArrayList<Long> intervalSum(int[] A,
                                   ArrayList<Interval> queries) {
    //Version 1. prefix sum,
    //Version 2. Segment tree: check Interval Sum II
    ArrayList<Long> result = new ArrayList<>();
    if (A == null || queries == null || A.length == 0 || queries.size() == 0) {
        return result;
    }
    Long[] prefixSum = new Long[A.length];
    Long sum = 0L;
    for (int i = 0; i < A.length; i++) {
        sum += A[i];
        prefixSum[i] = sum;
    }
    for (Interval interval : queries) {
        if (interval.start == 0) {
            result.add(prefixSum[interval.end]);
        } else {
            result.add(prefixSum[interval.end] - prefixSum[interval.start - 1]);
        }

    }
    return result;
}

Interval Sum II

Given an integer array in the construct method, implement two methods query(start, end) andmodify(index, value):

  • For query(start, end), return the sum from index start to index end in the given array.
  • For modify(index, value), modify the number in the given index to value

Example

Given array A = [1,2,7,8,5].

  • query(0, 2), return 10.
  • modify(0, 4), change A[0] from 1 to 4.
  • query(0, 1), return 6.
  • modify(2, 1), change A[2] from 7 to 1.
  • query(2, 4), return 14.

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge

O(logN) time for query and modify.

Solution: Segment Tree.

建立:O(n) 时间

查询:O(logN) 时间

更改其中一个元素: O(logN)

public class Solution {
    SegmentTreeNode root;

    public class SegmentTreeNode {
        int start, end;
        int sum;
        SegmentTreeNode left;
        SegmentTreeNode right;
        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public Solution(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        this.root = buildSegmentTree(A, 0, A.length - 1);
    }

    private SegmentTreeNode buildSegmentTree(int[] A, int start, int end) {
        SegmentTreeNode node = new SegmentTreeNode(start, end);
        if (start == end) {
            node.sum = A[start];
        } else {
            int mid = start + (end - start) / 2;
            node.left = buildSegmentTree(A, start, mid);
            node.right = buildSegmentTree(A, mid + 1, end);
            node.sum = node.left.sum + node.right.sum;
        }
        return node;
    }

    public long query(int start, int end) {
        if (start < this.root.start || end > this.root.end) {
            return -1;
        }
        return query(this.root, start, end);
    }

    private long query(SegmentTreeNode root, int start, int end) {
        if (root.start == start && root.end == end) {
            return root.sum;
        }
        int mid = root.start + (root.end - root.start) / 2;
        long leftSum = 0L, rightSum = 0L;
        if (start <= mid) {
            if (end <= mid) {
                leftSum = query(root.left, start, end);
            } else {
                leftSum = query(root.left, start, mid);
            }
        }
        if (end > mid) {
            if (start > mid) {
                rightSum = query(root.right, start, end);
            } else {
                rightSum = query(root.right, mid + 1, end);
            }
        }
        return leftSum + rightSum;
    }

    public void modify(int index, int value) {
        modify(this.root, index, value);
    }

    public void modify(SegmentTreeNode root, int index, int value) {
        if (root.start == index && root.end == index) {
            root.sum = value;
        } else {
            int mid = root.start + (root.end - root.start) / 2;
            if (index <= mid) {
                modify(root.left, index, value);
            } else {
                modify(root.right, index, value);
            }
            root.sum = root.left.sum + root.right.sum;
        }
    }
}

Segment Tree

Segment Tree(线段树)

性质:

  1. 二叉树
  2. 线段树的每个节点表示的是一段区间和最大值(或最小值)
  3. 节点的左子树 = 父亲区间分裂后的左区间

节点的右子树 = 父亲区间分裂后的右区间

查询:O(logN) 时间

  1. 查询的区间 和 线段树节点表示的区间 相等 -》直接返回节点的最大值
  2. 查询的区间 被 线段树节点表示的区间 包含 -》递归向下搜索左右子树
  3. 查询的区间 和 线段树节点表示的区间 不相交 -》停止搜索子树
  4. 查询的区间 和 线段树节点表示的区间 相交不相等 -》分裂查找左右子树 eg.max[1,3] = max([1,1], [2,3])

建立:O(n) 时间

  1. 自上而下递归分裂
  2. 自下而上回溯更新

Segment Tree Query

For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding SegmentTree, each node stores an extra attribute max to denote the maximum number in the interval of the array (index from start to end).

Design a query method with three parameters root, start and end, find the maximum number in the interval [start, end] by the given root of segment tree.

Example

For array [1, 4, 2, 3], the corresponding Segment Tree is:

<code>                  [0, 3, max=4]
                 /             \
          [0,1,max=4]        [2,3,max=3]
          /         \        /         \
   [0,0,max=1] [1,1,max=4] [2,2,max=2], [3,3,max=3]
</code>

query(root, 1, 1), return 4

query(root, 1, 2), return 4

query(root, 2, 3), return 3

query(root, 0, 2), return 4

Note

It is much easier to understand this problem if you finished Segment Tree Build first.

public int query(SegmentTreeNode root, int start, int end) {
    if (root == null) {
        return -1;
    }
    if (root.start == start && root.end == end) {
        return root.max;
    }
    int mid = root.start + (root.end - root.start) / 2;
    int leftMax = Integer.MIN_VALUE;
    int rightMax = Integer.MIN_VALUE;
    if (start <= mid) {
        if (end <= mid) {
            leftMax = query(root.left, start, end);
        } else {
            leftMax = query(root.left, start, mid);
        }
    }
    if (end > mid) {
        if (start >= mid) {
            rightMax = query(root.right, start, end);
        } else {
            rightMax = query(root.right, mid + 1, end);
        }
    }
    return Math.max(leftMax, rightMax);
}

Segment Tree Query II

For an array, we can build a SegmentTree for it, each node stores an extra attributecount to denote the number of elements in the the array which value is between interval start and end. (The array may not fully filled by elements)

Design a query method with three parameters root, start and end, find the number of elements in the in array’s interval [start, end] by the given root of value SegmentTree.

Example

For array [0, 2, 3], the corresponding value Segment Tree is:

<code>                     [0, 3, count=3]
                     /             \
          [0,1,count=1]             [2,3,count=2]
          /         \               /            \
   [0,0,count=1] [1,1,count=0] [2,2,count=1], [3,3,count=1]
</code>

query(1, 1), return 0

query(1, 2), return 1

query(2, 3), return 2

query(0, 2), return 2

Note

It is much easier to understand this problem if you finished Segment Tree Build and Segment Tree Query first.

public int query(SegmentTreeNode root, int start, int end) {
    if (root == null || start > root.end || end < root.start) {
        return 0;
    }
    if (root.start == start && root.end == end) {
        return root.count;
    }
    int mid = root.start + (root.end - root.start) / 2;
    int leftCount = 0, rightCount = 0;
    if (start <= mid) {
        if (end <= mid) {
            leftCount = query(root.left, Math.max(start, root.start), end);
        } else {
            leftCount = query(root.left, Math.max(start, root.start), mid);
        }
    }
    if (end >= mid) {
        if (start >= mid + 1) {
            rightCount = query(root.right, start, Math.min(end, root.end));
        } else {
            rightCount = query(root.right, mid + 1, Math.min(end, root.end));
        }
    }
    return leftCount + rightCount;
}

Segment Tree Modify

For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this node’s interval.

Implement a modify function with three parameter root, index and value to change the node’s value with [start, end] = [index, index] to the new given value. Make sure after this change, every node in segment tree still has the max attribute with the correct value.

Example

For segment tree:

<code>                      [1, 4, max=3]
                    /                \
        [1, 2, max=2]                [3, 4, max=3]
       /              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=3]
</code>

if call modify(root, 2, 4), we can get:

<code>                      [1, 4, max=4]
                    /                \
        [1, 2, max=4]                [3, 4, max=3]
       /              \             /             \
[1, 1, max=2], [2, 2, max=4], [3, 3, max=0], [4, 4, max=3]
</code>

or call modify(root, 4, 0), we can get:

<code>                      [1, 4, max=2]
                    /                \
        [1, 2, max=2]                [3, 4, max=0]
       /              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=0]
</code>
Note

We suggest you finish problem Segment Tree Build and Segment Tree Query first.

Challenge

Do it in O(h) time, h is the height of the segment tree.

Max Tree

Max Tree

Given an integer array with no duplicates. A max tree building on this array is defined as follow:

  • The root is the maximum number in the array
  • The left subtree and right subtree are the max trees of the subarray divided by the root number.

Construct the max tree by the given array.

Example

Given [2, 5, 6, 0, 3, 1], the max tree constructed by this array is:

<code>    6
   / \
  5   3
 /   / \
2   0   1
</code>
Challenge

O(n) time and memory.

Solution: 用stack来维护在每个数出现前比它大得数。

策略:

When new node comes in, if it is larger than the peek, stack.pop() and at the same time append it as the new node’s left child. until the stack peek is larger than the new node or the stack is empty, at this time, the peek.right = new node. then we push new node into the stack. if the stack is empty when the new node is pushed, the new node is the temporary root.

用7,3,8,2,4,5走一遍就理解了

public TreeNode maxTree(int[] A) {
    if (A == null || A.length == 0) {
        return null;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode root = null;
    for (int i = 0; i < A.length; i++) {
        TreeNode curr = new TreeNode(A[i]);
        while (!stack.isEmpty() && A[i] >= stack.peek().val) {
            TreeNode tmp = stack.pop();
            tmp.right = curr.left;
            curr.left = tmp;
        }
        if (!stack.isEmpty()) {
            stack.peek().right = curr;
        } else {
            root = curr;
        }
        stack.push(curr);
    }
    return root;
}

Leetcode: Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Recursive:

public class Solution {
 public boolean isSymmetric(TreeNode root) {
   if(root==null){
     return true;
   }
   return isSymmetric(root.left, root.right);
 }
 
 public boolean isSymmetric(TreeNode left, TreeNode right){
   if(left==null&&right==null){
     return true;
   }
   if((left==null&&right!=null)||(left!=null&right==null)){
     return false;
   }
   return left.val==right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
 }
}

 

Non-Recursive/Iteratively:


 

Leetcode: Convert Sorted Array to Binary Search Tree

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

public class Solution {
 public TreeNode sortedArrayToBST(int[] num) {
   return sortedArrayToBST(num, 0, num.length-1);
 }
 
 public TreeNode sortedArrayToBST(int[] num, int start, int end){
   if(start>end){
     return null;
   }
   int pivot = (start+end)/2;
   TreeNode root = new TreeNode(num[pivot]);
   root.left = sortedArrayToBST(num, start, pivot-1);
   root.right = sortedArrayToBST(num, pivot+1, end);
   return root;
 }
}

 

Leetcode: Balanced Binary Tree

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.

public class Solution {
 public boolean isBalanced(TreeNode root) {
   return getRebalancedHeight(root)==-1?false:true;
 }
 //getHeight for each node, -1 if it is already not balanced.
 public int getRebalancedHeight(TreeNode root){
 if(root==null){
   return 0;
 }
 int leftHeight = getRebalancedHeight(root.left);
 int rightHeight = getRebalancedHeight(root.right);
 if(leftHeight==-1||rightHeight==-1||Math.abs(leftHeight-rightHeight)>1){
   return -1;
 }
   return Math.max(leftHeight, rightHeight)+1;
 }
}