Leetcode:124. 두 갈래 나무의 최대 경로와

제목: 비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다.본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다.예 1: 입력: [1,2,3]

   1
  / \
 2   3

출력: 6 예 2: 입력: [-10,9,20,null,null,15,7]
-10/ 9 20/ 15 7
출력: 42
학습, 코드
이해:1.두 갈래 트리의 한 노드에서 다른 노드로 가는 경로는 반드시 두 노드의 부모 노드를 통과해야 한다.2. 경로는 한 하위 노드에서 이 하위 노드의 부모 노드로... 마지막 부모 노드를 제외하고 다른'부'노드는 한 하위 트리만 지나갈 수 있다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        backtrack(root);
        return max;
    }
    private int backtrack(TreeNode root){
        if(root == null) return Integer.MIN_VALUE;
        int left = backtrack(root.left);
        int right = backtrack(root.right);
       // ： ， root ， int left,right pick root  
       //  。max = Math.max(max,Math.max(right,left));       //pick left branch or right branch
        max = Math.max(max,root.val);                   //pick root
        max = Math.max(max,root.val+Math.max(0,left)+ Math.max(0,right)  ); // pick root + MAX(0,left) + MAX(0,right)
        return root.val + Math.max(0,Math.max(left,right));
    }
}

4.10 검토

class Solution {
    int max=Integer.MIN_VALUE;// MIN_VALUE 
    
    public int maxPathSum(TreeNode root) {
        dg(root);
        
        return max;
    }
    
    public int dg (TreeNode root){
        if(root==null)return 0;

        int left=dg(root.left);
        int right=dg(root.right);
        
        //if(root.left!=null)left=root.left.val;// ： ， 
        //if(root.right!=null)right=root.right.val;//
        
        max=Math.max(root.val,max);// ；
        
        max=Math.max(root.val+Math.max(left,0),max);//Math.max(left,0) ， +left ； // 
        max=Math.max(root.val+Math.max(right,0),max); // 
        
        max=Math.max(root.val+Math.max(left,0)+Math.max(right,0),max); // ；
            
            
        return root.val+Math.max(Math.max(left,right),0); // ， 
           
    }