Binary Tree & Binary Search Tree)

15290 단어
1. Invert Binary Tree Invert Binary Tree# 즉 두 갈래 트리를 출력하는 거울 솔루션:root 노드는 변하지 않고 왼쪽 노드와 오른쪽 노드가 서로 바뀐다.그리고 왼쪽 트리와 오른쪽 트리를 나누어 invert(귀속)
class Solution {
    public TreeNode invertTree(TreeNode root) {
        //recursion terminator
        //current level processing
        //dirll down
        if (root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

2. 두 갈래 나무의 거울 여부 판단 [Symmetric Tree]https://leetcode.com/problems/symmetric-tree/description/solution: 귀속, 코드 보기
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }
    public boolean isMirror(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && isMirror(p.left,q.right) && isMirror(p.right,q.left);
    }
}

3. Valid Binary Search Tree Valid Binary Search Tree solution: 귀속, 각각 root 판단.left ,root,root.right
class Solution {
    public boolean isValidBST(TreeNode root) {
        // stack &  
        // 
        if (root == null) {
            return true;
        }
        Stack stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pre != null && root.val <= pre.val) {
                return false;
            }
            pre = root;
            root = root.right;
        }
        return true;
    }
}

4. 두 갈래 검색 트리에서 K의 작은 요소 [Kth Smallest Element in a BST]https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/solution: 왼쪽 노드가 루트 노드보다 작고 오른쪽 노드보다 작기 때문에 두 갈래 검색 트리의 특징 중 하나는 중순으로 흐르는 결과가 바로 트리 안의 노드가 작은 순서에서 큰 순서로 출력되는 결과입니다.여기는 교체 형식을 채택하면 우리는 k소노드를 찾을 때 바로 퇴장할 수 있다.
class Solution {
    public int kthSmallest(TreeNode root, int k) {
       Stack stack = new Stack<>();
       while(root != null || !stack.isEmpty()) {
           while(root != null) {
               stack.push(root);    
               root = root.left;   
           } 
           root = stack.pop();
           if(--k == 0) break;
           root = root.right;
       }
       return root.val;
    }
}

5. 두 갈래 나무의 중차 반복solution:stack을 이용하여
class Solution {
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList();
        if (root == null) {
            return list;
        }
        Stack stack = new Stack();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

6. Maximum Depth of Binary Tree solution: 귀속, 왼쪽 트리 깊이에 오른쪽 트리 깊이
class Solution {
    public int maxDepth(TreeNode root) {
        // 
        if (root == null) {
            return 0;
        }
        
        return Math.max(maxDepth(root.left) , maxDepth(root.right)) + 1;
        // Math.max() 
    }
}

Minium Depth 문제 첨부, 차이점 주의
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        if (root.left == null && root.right != null) {
            return minDepth(root.right) + 1;
        }
        if (root.left != null && root.right == null) {
            return minDepth(root.left) + 1;
        }
        return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
    }
}

7. Convert sorted list to Binary Search Tree solution: 빠른 포인터, 빠른 포인터가 끝났을 때 마침 느린 포인터가 중점까지 간 다음에 중점을 두 갈래 나무의 뿌리 노드로 하고 좌우 양쪽으로 돌아가기 Convert sorted list to Binary Search Tree
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        //recurison
        if (head == null) {
            return null;
        }
        return toBST(head,null);
    }
    public TreeNode toBST(ListNode head,ListNode tail) {
        ListNode slow = head;
        ListNode fast = head;
        if (head == tail) {
            return null;
        }
        while (fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode thead = new TreeNode(slow.val);
        thead.left = toBST(head,slow);
        thead.right = toBST(slow.next,tail);
        return thead;
    }

8. Convert Sorted Array to Binary Search Tree Convert Sorted Array to Binary Search Tree solution: 중점을 찾아서 주의해야 할 것은 수조가 두 갈래로 변하는 함수 toBST(nums, 0, nums.length-1), 주의 방법
class Solution {
    
    public TreeNode sortedArrayToBST(int[] nums) {
        //recursion
        if (nums == null) {
            return null;
        }
        return toBST(nums, 0, nums.length - 1);      
    }
    public TreeNode toBST(int[] nums, int start ,int end) {
        if (start > end) {
            return null;
        }
        TreeNode thead = new TreeNode(nums[(start + end) / 2]);
        thead.left = toBST(nums, start, (start + end) / 2 - 1);
        thead.right = toBST(nums, (start + end) / 2 + 1, end);
        return thead;
    }
}

9.Lowest Common Ancestor of a Binary Search Tree Lowest Common Ancestor of a Binary Search Tree solution: 귀속, 코드 이해
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

10.Lowest Common Ancestor of a Binary Tree [Lowest Common Ancestor of a Binary Tree]https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/solution: 기본적인 사고방식은 한 문제와 같다. 단지 이 문제는 일반적인 두 갈래 나무이기 때문에 두 노드와 뿌리 노드의 크기 관계를 비교할 수 없다.아니면 최근 공공자 노드가 좌우자 나무에 나타났는지 판단해야 한다.
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        if (root == p || root == q) {
            return root;
        }
        // 
        // 
        TreeNode left = lowestCommonAncestor(root.left, p, q) ;
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 
        if ( left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }
}

11. 다른 수를 판단하는 자수 [Subtree of Another Tree]https://leetcode.com/problems/subtree-of-another-tree/description/solution: 자나무는 반드시 잎결점에서 시작해야 한다. 중간 부분의 어떤 부분은 자나무라고 할 수 없다. 그러면 우리는 사고방식을 바꾸자. s의 어떤 결점에서 시작하고 t의 모든 구조와 같다. 그러면 문제는 두 나무가 같은지, 즉Same Tree를 판단하는 문제로 바뀌었다. 이 점을 납득하면 코드는 쓰기 쉽다. 귀속으로 매우 간결하게 쓴다. 우리는 먼저 s의 뿌리결점부터 시작한다.t와 비교하면 만약에 두 나무가 완전히 같다면true를 되돌려준다. 그렇지 않으면 각각 s의 왼쪽 결점과 오른쪽 결점에 대해 귀속을 호출하여 다시 한 번 동일한지 판단하고true를 되돌려주면 찾을 수 있음을 나타낸다.
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        if (isSame(s, t)) return true;
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    
    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        
        if (s.val != t.val) return false;
        
        return isSame(s.left, t.left) && isSame(s.right, t.right);
    
    }
}

12. 두 갈래 나무 검지offer 버전solution: 매번에 하나의 결점을 인쇄할 때, 이 결점에 자결점이 있다면, 이 결점의 자결점을 하나의 대열의 끝에 놓는다.다음은 대기열의 머리에서 가장 먼저 대기열에 들어간 결점을 꺼내고 대기열의 모든 결점이 인쇄될 때까지 앞의 인쇄 작업을 반복합니다.
public static void printFromToBottom(BinaryTreeNode root) {
        //  
        if (root != null) {
            //  
            Queue list = new LinkedList<>();
            //  
            list.add(root);
            //  
            BinaryTreeNode curNode;
            //  
            while (!list.isEmpty()) {
                //  
                curNode = list.remove();
                //  
                System.out.print(curNode.value + " ");
                //  , 
                if (curNode.left != null) {
                    list.add(curNode.left);
                }
                //  , 
                if (curNode.right != null) {
                    list.add(curNode.right);
                }
            }
        }
    }

13. 두 갈래 트리를 여러 줄 검지 offer 버전으로 인쇄하기solution: 대기열 구현, 너비 유한 검색, 주석 보기
public static void print(BinaryTreeNode root) {
        if (root == null) {
            return;
        }
        List list = new LinkedList<>();
        BinaryTreeNode node;
        //  
        int current = 1;
        //  
        int next = 0;
        list.add(root);
        while (list.size() > 0) {
            node = list.remove(0);
            current--;
            System.out.printf("%-3d", node.val);
            if (node.left != null) {
                list.add(node.left);
                next++;
            }
            if (node.right != null) {
                list.add(node.right);
                next++;
            }
            if (current ==0) {
                System.out.println();
                current = next;
                next = 0;
            }
        }
    }
@ 
public void levelorder(TreeNode root) { // BFS
    Queue queue = new LinkedList<>();
    
    queue.offer(root);
    int level = 0;
    
    while (!queue.isEmpty()) {
        System.out.printf("Level %d
", level++); Queue queue2 = new LinkedList<>(); while (!queue.isEmpty()) { TreeNode top = queue.poll(); System.out.printf("%d ", top.val); if (top.left != null) queue2.offer(top.left); if (top.right != null) queue2.offer(top.right); } queue = queue2; } }

14. 두 갈래 나무를 체인 테이블 솔루션으로 변경: 코드 보기
class Solution {
    private TreeNode prev = null;
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
}

15. 두 갈래 검색 트리 복원 [Recover a Binary Search Tree]https://leetcode.com/problems/recover-binary-search-tree/description/솔루션: 해결 방법은 중간 순서를 이용하여 순서가 틀린 두 가지를 훑어보는 것입니다. 마지막으로 swap하면 됩니다.이 중간의 잘못은 두 개의 점을 교환했기 때문에 큰 것은 앞으로 왔고 작은 것은 뒤로 갔다.그래서 중서가 편리할 때 만나는 첫 번째 순서는 상쇄된 두 개의 node입니다. 큰 것은 틀림없이recovery의 그 중 하나입니다. 기록해야 합니다.또 하나는 온전한 나무를 두루 돌아다니며 마지막 역순의 node를 기록해야 한다.간단하게 말하면 첫 번째 역순점은 기록해야 하고, 마지막 역순점은 기록해야 하며, 마지막 swap은 기록해야 한다.
class Solution {
    TreeNode pre;
    TreeNode first;
    TreeNode second;
    
    public void recoverTree(TreeNode root) {
        pre = null;
        first = null;
        second = null;
        inorder(root);
        if (first != null && second != null) {
            int tmp = first.val;
            first.val = second.val;
            second.val = tmp;
        }
    }
    public void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        if(pre == null) {
            pre = root;//pre 
        } else {
            if(pre.val > root.val) {
                if ( first == null) {
                    first = pre;// 
                }
                second = root;// 
            }
            pre = root;
        }
        inorder(root.right);       
    }   
}

16. 루트 노드에서 잎 노드까지의 경로를 계산합니다. 이 경로의 합은 상수solution과 같습니다. 분리, 왼쪽 트리 경로는sum-root와 같습니다.val, 또는 오른쪽 트리에서 경로를sum-root와 같은 경로로 찾습니다.val [Path Sum]https://leetcode.com/problems/path-sum/description/
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.val == sum && root.left == null && root.right == null) {
            return true;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum -root.val);

    }
}

17. 트리의 후속은 LeetCode 버전solution: 창고를 유지하고 그 안에 트리의 노드를 저장합니다.창고에서 나온 노드를 저장할 목록을 유지합니다.
class Solution {
    public List postorderTraversal(TreeNode root) {
        // 
        LinkedList ans = new LinkedList<>();
        Stack stack = new Stack<>();
        if (root == null) return ans;
    
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            ans.addFirst(cur.val);
            if (cur.left != null) {
                stack.push(cur.left);
        }
        if (cur.right != null) {
            stack.push(cur.right);
        } 
    }
    return ans;
    }
}

18. 두 갈래 나무의 다음 노드solution: (제의: 두 갈래 나무와 그 중의 한 결점을 정하고 어떻게 중간 순서가 차례대로 흐르는 다음 결점을 찾습니까? 나무의 결점은 좌우 자결점을 가리키는 두 개의 바늘 이외에 부모 노드를 가리키는 바늘이 있습니다.)만약 결점에 오른쪽 나무가 있다면, 그 다음 결점은 바로 오른쪽 나무의 왼쪽 결점이다.즉, 오른쪽 결점에서 출발하여 왼쪽 결점을 가리키는 지침을 따라 가면 우리는 그 다음 결점을 찾을 수 있다.이어서 우리는 결점에 오른쪽 나무가 없는 상황을 분석했다.만약 결점이 아버지 노드의 왼쪽 자식 결점이라면, 그 다음 결점은 바로 아버지 결점이다.만약 결점이 오른쪽 나무도 없고, 그것도 아버지 결점의 오른쪽 결점이라면, 이런 상황은 비교적 복잡하다.우리는 아버지 노드를 가리키는 바늘을 따라 아버지 결점의 왼쪽 자 결점을 찾을 때까지 계속 위로 올라갈 수 있다.만약 이런 결점이 존재한다면, 이 결점의 부결점은 우리가 찾는 다음 결점이다.
public static BinaryTreeNode getNext(BinaryTreeNode node) {
        if (node == null) {
            return null;
        }
        //  
        BinaryTreeNode target = null;
        if (node.right != null) {
            target = node.right;
            while (target.left != null) {
                target = target.left;
            }
            return target;
        } else if (node.parent != null){
            target = node.parent;
            BinaryTreeNode cur = node;
            //  , , 
            while (target != null && target.left != cur) {
                cur = target;
                target = target.parent;
            }
            return target;
        }
        return null;
    }

좋은 웹페이지 즐겨찾기