[LeetCode] 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.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

 解题思路：
 1. 对于任何一个node, 有四种path情况需要考虑：
  1.1 仅有node
  1.2 左子树+node
  1.3 node + 右子树
  1.4 左子树 + node + 右子树

为了求最大的path sum. 我们需要从1-3中选出最大的返回给parent，从1-4中选出最大的作为备选的最后结果path sum.

Java Code:

public int maxPathSum(TreeNode root){
       int[] max = new int[1];
       max[0] = Integer.MIN_VALUE;
       maxSum(root, max);
       
       return max[0];
    }
    
    public int maxSum(TreeNode root, int[] max){
        int val = 0, left = 0, right = 0;
        
        val = root != null ? root.val : 0;   
        left = root.left != null? maxSum(root.left, max) : 0;
        right = root.right != null ? maxSum(root.right, max) : 0;
        
        int currMax = val;
        
        if(left > 0) currMax += left;
        if(right > 0) currMax += right;
        max[0] = max[0] > currMax? max[0] : currMax;
        
        if(left > 0 && left >= right) return val + left;
        if(right > 0 && right > left) return val + right;
        
        return val;
    }
    

[LeetCode] 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?

解题思路：
DSF,  先把所有的左结点存放到stack, pop的时候，print 当前位置的值，然后再遍历右子树

Java Code:

 public List inorderTraversal(TreeNode root) {
          Stack tmp = new Stack();
          List res = new ArrayList();
          
          TreeNode p = root;
          
          while( !tmp.isEmpty() || p != null ){
              while(p != null){
                  tmp.add(p);
                  p = p.left;
              }
           
               p = tmp.pop();
               res.add(p.val);
               p = p.right;
           
          }
          
        return res;
    }