Bottom up 주제 1 Leet Code124.Binary Tree Maximum Path Sum

bottom up의 방법은 모든 node에 저장해야 할 데이터를 새로운 클래스에 기록하는 것을 말한다. dfs를 할 때 각 노드에서 본 노드의 조작을 한 다음에 새로운 클래스의 대상을 만들고 대상에 기록해야 할 데이터를 모두 부여한 다음에 본 노드로 돌아가면 된다.마지막으로 루트로 돌아갈 때 루트 노드의 대상에서 필요한 값을 직접 꺼내면 됩니다.

LeetCode 124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes 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: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

다음은res[0]를 전역 변수로 업데이트하고 helper 함수가 현재 노드를 포함하는 값을 되돌려줍니다.

    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        int[] res = new int[]{Integer.MIN_VALUE};
        helper(root, res);
        return res[0];
    }
    private int helper(TreeNode root, int[] res) {
        if (root == null) return 0;
        int left = helper(root.left, res) + root.val;
        int right = helper(root.right, res) + root.val;
        int max = Math.max(left, right);
        max = Math.max(max, left + right - root.val);
        max = Math.max(root.val, max);
        res[0] = Math.max(res[0], max);
        return Math.max(left, Math.max(root.val, right));
    }

표준판: 반드시 현재 node에서 현재 답안을 어떻게 갱신하는지 알아야 한다!!!분석 제목에서 우리가 모든 노드에 저장해야 하는 수치는 이 노드를 포함하는 pathsum의 최대 값이기 때문에 가능성은 다음과 같다. (1) 이 노드만 있고, (2) 이 노드 + 왼쪽 아이, (3) 이 노드 + 오른쪽 아이만 있다.동시에 최대치 즉 답을 갱신해야 한다. 가능성은 (1) 이 노드만 있고, (2) 이 노드 + 왼쪽 아이, (3) 이 노드 + 오른쪽 아이, (4) 이 노드 + 왼쪽 아이 + 오른쪽 아이, (5) 왼쪽 아이의 최대치, (6) 오른쪽 아이의 최대치를 포함한다.

    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        return dfs(root).res;
    }
    private Result dfs(TreeNode root) {
        if (root == null) return new Result(Integer.MIN_VALUE, 0);
        
        Result result = new Result(Integer.MIN_VALUE, Integer.MIN_VALUE);
        
        Result left = dfs(root.left);
        Result right = dfs(root.right);
        
        int _res = Math.max(left.cur + root.val, right.cur + root.val);
        int _res1 = Math.max(right.res, left.res);
        _res = Math.max(_res, left.cur + right.cur + root.val);
        _res = Math.max(_res, root.val);
        _res = Math.max(_res, _res1);
        
        
        int _cur = Math.max(left.cur + root.val, right.cur + root.val);
        _cur = Math.max(_cur, root.val);
        
        result.cur = _cur;
        result.res = _res;
        
        return result;
    }
    private class Result{
        int res;
        int cur;
        public Result(int res, int cur) {
            this.res = res;
            this.cur = cur;
        }
    }