문제를 풀다--두 갈래 나무(1)

두 갈래 나무의 문제는 기본적으로 깊이 우선 검색이다
두 갈래 나무에서 값을 구하고 경로를 구하다
max/min/averge/sum/path
두 갈래 나무 구조 변화
두 갈래 찾기 트리 BST
 
traversal 역귀는 반환 값이 없습니다. 전역 변수가 필요합니다.
divide & conquer 반환값 분할
 
분치법 - 두 갈래 나무 문제에 부딪히면 나무 전체의 문제적 결과와 좌우 나무의 이 문제적 결과 간의 관계가 무엇인지 생각해 보자
 
한두 갈래 나무에서 값을 구하고 경로를 구하다
예: lintcode 596.Minimum Subtree https://www.lintcode.com/problem/minimum-subtree/description
traversal + divide conquer . traversal은 전체적인 변수로 도전하는 데 나타난다. 분치의 사상은 매번 좌우 나무의 최소화를 구하는 것이지 두루 돌아다니는 것이 아니다.좌우 트리의 최소 값을 귀속적으로 구해야 하기 때문에 귀속 함수는 반환 값이 필요하다.만약 단순하게divideconquer를 사용한다면, 반환값의 형식은 문제 답안의 형식이어야 한다. 왜냐하면 전역 변수가 없기 때문이다.여기에는 과정 중에 필요한 값의 유형이 될 수 있다.
매번 좌우 나무의 합을 구한 후에 전체 변수와 도전하면 된다.

public class Solution {
    /**
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
    /*divdie conquer(recursion on left and right) + traversal(global variable )*/
    private int minSum = Integer.MAX_VALUE;
    private TreeNode res = null;
    
    public TreeNode findSubtree(TreeNode root) {
        helper(root);
        return res;
    }
    
    public int helper(TreeNode root){
        if(root == null){
            return 0;
        }
        
        int left = helper(root.left);
        int right = helper(root.right);
        
        int sum = left + right + root.val;
        if(sum < minSum){
            minSum = sum;
            res = root;
        }
        
        return sum;
    }

 
 
두 번째divide conquer
답안 유형은 TreeNode이고 문제풀이에서 int의 크기를 비교해야 하기 때문에class를 만들어서 필요한 변수를 넣어야 합니다.
분치의 사상은 좌우 나무의 구별의 최소화와 루트를 얻는 데 있다.val + 좌우 트리의 모든 합, 세 값을 비교하여 왼쪽 트리의 가장 작은 합, 오른쪽 트리의 가장 작은 합, 또는 루트를 되돌려줍니다.class에는 자수의 최소화, 자수의 최소화 머리, 자신의 전부와 세 가지 변수가 필요합니다.

    class Subtree{
        int minSum;
        TreeNode minRoot;
        int rootSum;
        public Subtree(int minSum, TreeNode minRoot, int rootSum){
            this.minSum = minSum;
            this.minRoot = minRoot;
            this.rootSum = rootSum;
        }
    } 
    
    public TreeNode findSubtree(TreeNode root) {
        Subtree res = helper(root);
        return res.minRoot;
    }
    
    public Subtree helper(TreeNode root){
        if(root == null){
            return new Subtree(Integer.MAX_VALUE, null, 0);
        }
        
        Subtree left = helper(root.left);
        Subtree right = helper(root.right);
        
        Subtree res = new Subtree(
            left.rootSum + right.rootSum + root.val,
            root,
            left.rootSum + right.rootSum + root.val
            );
        
        if(res.minSum > left.minSum){
            res.minSum = left.minSum;
            res.minRoot = left.minRoot;
        }
        
        if(res.minSum > right.minSum){
            res.minSum = right.minSum;
            res.minRoot = right.minRoot;
        }
        
        return res;
        
    }

 
 
예: lintcode 480.Binary Tree Paths https://www.lintcode.com/problem/binary-tree-paths/description
모든 뿌리에서 잎으로 가는 경로 찾기
traversal의 사고방식: 뿌리에서 시작하여 좌우로 recursion을 향해 내려가면 노드가 기록(String)에 현재 루트의 값을 추가합니다.null에 도착했을 때, 이 경로를 결과에 집중하세요.recursion function의 매개 변수는 최종적으로 되돌아오는 결과 집합 목록을 포함하는데, 이것은 전역 변수와 같은 효과입니다.

    public List binaryTreePaths(TreeNode root) {
        List res = new ArrayList<>();
        if(root == null)return res;
        
        helper(root, String.valueOf(root.val), res);
        
        return res;
    }
    
    public void helper(TreeNode root, String path, List res){
        
        if(root.left == null && root.right == null){
            res.add(path);
            return;
        }
        
        if(root.left != null){
            helper(root.left, path +"->"+ root.left.val,res);
        }
        
        if(root.right != null){
            helper(root.right, path +"->"+ root.right.val,res);
        }
    }

 
divde conquer: 분리된 사고방식은 좌우 트리의 모든 경로에 루트 자체의val를 추가하는 것입니다.반환값은 문제 답안의 유형이고 좌우 트리 리커션의 반환값은 결과집입니다.null일 때 빈 결과 집합을 되돌려줍니다.잎 노드는 자신의 결과집만 포함하는 것으로 되돌아가야 한다.빈 결과집으로 돌아갈 때 자신을 더듬을 방법이 없기 때문에 잎 노드인지 아닌지를 한 번 더 판단해야 한다.

 public List binaryTreePaths(TreeNode root) {
        List res = new ArrayList<>();
        if(root == null)return res;
        
        return helper2(root);
    }
    
    public List helper2(TreeNode root){
        List res = new LinkedList<>();
        if(root == null){
            return res;
        }
        
        List leftRes = helper2(root.left);
        List rightRes = helper2(root.right);
        
        for(String s : leftRes){
            //s = root.val + "->" + s;
            res.add(root.val + "->" + s);
        }
        
        for(String s : rightRes){
            //s = root.val + "->" + s;
            res.add(root.val + "->" + s);
        }
        
        if(res.size() == 0){
            res.add(root.val + "");
        }
        
        return res;
    }

follow up에서 String을 StringBuilder로 변경합니다.
시간 복잡도 O(nlogn)가 최대입니다.두 갈래 나무,traversal 방법, 즉 n/2개의 잎 노드, n/2개의 경로, 모든 경로는 O(logn)의 시간으로 값을 붙여야 하고,divideconquer 방법, 모든 점은 자신의 모든 경로를 한 번씩 훑어보아야 하며, 모두 n/2개의 경로에 해당하며, 각 층마다 한 번씩 훑어보아야 한다.
경로를 찾을 때 O (경로 수 * 각 경로를 구성하는 시간)
점 찾기 O(n* 점당 처리 시간)
 
예: lintcode 88.Lowest Common Ancestor of a Binary Tree  https://www.lintcode.com/problem/lowest-common-ancestor-of-a-binary-tree/description
traversal: 먼저 훑어보는 순서로 노드를 걸을 때마다 값과 대응하는 등급을 기록하고 값의 기록에서 AB 한 쌍을 찾습니다. 둘 중 등급이 가장 높은 것은 lowestcommon ancestor입니다.
divide conquer:
우선 상황을 고려해 보면 만약에 직설적으로 생각하면 리커션은 LCA 또는null로 돌아가고 AB는 모두 왼쪽 나무에 있고 왼쪽 나무는 LCA로 돌아가고 오른쪽 나무는null로 돌아간다.AB는 모두 오른쪽 나무, 오른쪽 나무는 LCA, 왼쪽 나무는null로 돌아간다.AB는 각각 왼쪽 나무와 오른쪽 나무에 있는데 모두 LCA가 없고 모두null로 돌아간다. 그러면 LCA는 root이다.마지막 상황은 좌우 나무에 AB가 없는데 모두 null로 돌아오면 위의 상황과 충돌한다.
그래서 다른 생각으로 리큐션이 A나 B에 도착했을 때 A나 B로 되돌아가고, 리큐션의 종료는 물론null을 만나서null로 되돌아간다.좌우가null일 때null로 되돌아오기;좌우 나무는 단지 하나가null이 아니면 그것이 아닌 것으로 돌아간다.만약 모두null이 아니라면, LCA를 찾아서 루트로 돌아가는 것입니다.

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if(root == A || root == B) return root;
        return helper(root, A, B);
    }
    
    public TreeNode helper(TreeNode root, TreeNode A, TreeNode B){
        if(root == null)return null;
        
        if(root == A || root == B)return root;
        
        TreeNode left = helper(root.left, A, B);
        TreeNode right = helper(root.right, A, B);
        
        if(left == null && right == null){
            return null;
        }
        
        if(left == null && right != null){
            return right;
        }
        
        if(right == null && left != null){
            return left;
        }
        
        return root;
    }
}

예: lintcode 578.Lowest Common Ancestor https://www.lintcode.com/problem/lowest-common-ancestor-iii/description?_from=ladder&&fromId=1
88의 문제풀이 성립될 수 있는 전제조건은 반드시 AB가 있다는 것이다. 만약 하나만 있다면 결국 그 하나를 되돌릴 것이다.
문제 풀이에서 AB가 있는지 알아야 하기 때문에recursion에서 이 정보를 전달해야 하기 때문에class를 만들면 LCA와 AB가 존재하는지 여부를 포함한다

    class IsContain{
        TreeNode LCA;
        boolean isA;
        boolean isB;
        public IsContain(TreeNode LCA, boolean isA, boolean isB){
            this.LCA = LCA;
            this.isA = isA;
            this.isB = isB;
        }
    } 
     
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        IsContain res = helper(root, A, B);
        if(!res.isA || !res.isB){
            return null;
        }else{
            return res.LCA;
        }
    }
    
    public IsContain helper(TreeNode root, TreeNode A, TreeNode B){
        if(root == null){
            return new IsContain(null, false,false);
        }

        IsContain left = helper(root.left, A, B);
        IsContain right = helper(root.right, A, B);
        
        boolean isANow = left.isA||right.isA||root == A;
        boolean isBNow = left.isB||right.isB||root == B;
        
        if(root == A){
            return new IsContain(A, isANow, isBNow);
        }
        if(root == B){
            return new IsContain(B, isANow, isBNow);
        }
        
        if(left.LCA == null && right.LCA == null){
            return new IsContain(null,isANow,isBNow);
        }
        
        if(left.LCA != null && right.LCA != null){
            return new IsContain(root, true, true);
        }
        
        if(left.LCA != null){
            return new IsContain(left.LCA,isANow,isBNow);
        }
        
        return new IsContain(right.LCA, isANow, isBNow);
    }
}