Binary Tree Postorder Traversal

Similar to inorder and preorder traversal. Key point is to keep track of visited right child, by using one node. This is code ganker's idea.

When I started to attack this question, I tried to use a hashset to record all visited nodes, which is less space efficient than code ganker's code.

Below is my code(just for reference):

 public class Solution {  
   public List<Integer> postorderTraversal(TreeNode root) {  
     LinkedList<TreeNode> stack = new LinkedList<TreeNode>();  
     HashSet<TreeNode> visitedNodes = new HashSet<TreeNode>();  
     ArrayList<Integer> res = new ArrayList<Integer>();  
     while(root != null || !stack.isEmpty()){  
         stack.push(root);  
         if(root.left == null || visitedNodes.contains(root.left)){// try go right child  
           if(root.right == null || visitedNodes.contains(root.right)){// if right child visited or null  
             root = stack.pop();  
             res.add(root.val);  
             visitedNodes.add(root);  
             if(stack.isEmpty()) return res;  
             root = stack.pop();  
           }  
           else{  
             root = root.right;  
           }  
         }  
         else{  
           root = root.left;  
         }  
     }  
     return res;  
   }  
 }  

Best Time to Buy and Sell Stock

Key point is to keep track of the smaller "buying price" and update profit when current price can make more money if sold out. DP is usually applied when we need to find out some optimized value, like max or min. profits[i] means max profit by ith day.

 public class Solution {  
   public int maxProfit(int[] prices) {  
     if (prices == null || prices.length <= 1) return 0;  
     int buy_idx = 0;  
     int[] profits = new int[prices.length];  
     profits[0] = 0;  
     profits[1] = Math.max(0, prices[1] - prices[buy_idx]);  
     buy_idx = profits[1]>0?0:1;  
     for(int i = 2; i < prices.length; i ++){  
       profits[i] = profits[i - 1];  
         if (prices[i] < prices[buy_idx]) buy_idx = i;  
         if ((prices[i] - prices[buy_idx]) > profits[i]){  
           profits[i] = prices[i] - prices[buy_idx];  
         }  
     }  
     return profits[prices.length - 1];  
   }  
 }  

code ganker's post about this question: http://blog.csdn.net/linhuanmars/article/details/23162793
His answer is much better, with only O(1) space. And the idea is simpler and more general. Key point he proposes is local optimization and global optimization.

A better and general explanation can be found in the 3rd version of this problem: http://blog.csdn.net/linhuanmars/article/details/23236995

Triangle

At first glance, I thought it is recursion problem, since it is related to or similar with the "Tree" structure. So this time my code is like below:

 public class Solution {  
   public int minimumTotal(List<List<Integer>> triangle) {  
     if (triangle == null) return 0;  
     if (triangle.size() == 1) return triangle.get(0).get(0);  
     ArrayList<Integer> list = new ArrayList<Integer>();  
     WrapInt wi = new WrapInt(Integer.MAX_VALUE);  
     findMinSum(triangle, 0, 0, wi, list);  
     return wi.val;  
   }  
   public void findMinSum(List<List<Integer>> triangle, int level, int idx, WrapInt wi, ArrayList<Integer> list){  
     list.add(triangle.get(level).get(idx));  
     if (list.size() == triangle.size()){  
       int sum = 0;  
       for (int e : list){  
         sum += e;  
       }  
       if (sum < wi.val) wi.val = sum;  
       return;  
     }  
     findMinSum(triangle, level + 1, idx , wi, list);  
     list.remove(list.size() - 1);  
     findMinSum(triangle, level + 1, idx+1, wi, list);  
     list.remove(list.size() - 1);  
   }  
 }  
 class WrapInt{  
   int val;  
   public WrapInt(int v){  
     val = v;  
   }  
 }  

Apparently, this is not very efficient. It is like a brute force answer, with all possible results been computed. Time complexity should be O(2^(n - 1)). NO!! Too much time.

Now we can know that we must waste time in computing redundant path, or duplicate computing. To improve recursion version, DP is usually applied.

Thanks again for code ganker's good job.  Key point is sum[i][j](the "min sum value" at level i, index j) is equal to min(sum[i-1][j-1], sum[i-1][j]) + triangle[i][j]. This is a bottom-to-up idea. For each level, calculation is based on previous level. Overall, each element is traversed once, so time is O(n^2), and using an array can keep space O(n)

Hope I can think of this idea by myself next time.

124 Binary Tree Maximum Path Sum

Hello, guys. It has been such a long time since this blog was updated. Solving problems is an endless adventure. I am really happy that I am still in the trip.

Back to our topic, let's take a look at this problem in leetcode.

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any node sequence from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

 

Example 1:

Input: root = [1,2,3]
Output: 6

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42

 

Constraints:

• The number of nodes in the tree is in the range [0, 3 * 104].
• -1000 <= Node.val <= 1000

Dealing with problems of tree usually needs recursion as a hand. This is due to the special structure of tree. The structure of tree is also a recursion.

Thanks to code ganker's helpful tips.  One key point of this question is that if max sum of one root can be max sum of left subtree, plus value of root, plus max sum of right subtree, however, when one node is needed to connect to its parent, only its left or right subtree, plus its own value should be used.  Another good point I didn't think of is that if left or right subtree return negative value, root would add nothing than adding negatives.

Below is the code:

 public class Solution {  
   public int maxPathSum(TreeNode root) {  
     if (root == null) return 0;  
     ArrayList<Integer> res = new ArrayList<Integer>();  
     res.add(Integer.MIN_VALUE);  
     helper(root,res);  
     return res.get(0);  
   }  
   public int helper(TreeNode root, ArrayList<Integer> res){  
     if (root == null) return 0;  
     int left = helper(root.left, res);  
     int right = helper(root.right, res);  
     int result = root.val + (left>0?left:0) + (right>0?right:0);  
     if (result > res.get(0)){  
       res.set(0, result);  
     }  
     return root.val + Math.max(left, Math.max(right,0));  
   }  
 }  

UPDATED: my answer in late 2020

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return maxSum;
    }
    
    private int[] helper(TreeNode node) {
        int[] result = new int[2];
        if (node == null) {
            return result;
        }
        int[] leftResult = helper(node.left);
        int[] rightResult = helper(node.right);
        // sum value can be connected to parent
        // note: parent can choose to ignore negative values
        result[0] = node.val + Math.max(0, Math.max(leftResult[0], rightResult[0]));
        // sum value disconnected to parent
        result[1] = node.val + Math.max(0, leftResult[0]) + Math.max(0, rightResult[0]);
        
        maxSum = Math.max(maxSum, result[1]);
        return result;
    }
}