두 갈래 나무에 대한 문제풀이 노트,Python 구현

두 갈래 나무의 정의

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

98. 두 갈래 검색 트리 검증 바이너리 검색 트리

LeetCodeCN 98번 링크
첫 번째 방법: 중간 순서로 두 갈래 나무를 옮겨다니며 수조에 저장하고 직접 상승 순서로 정렬하여 중량을 제거한 원래의 두 갈래 나무와 비교한다

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        inorder = self.inorder(root)
        return inorder == list(sorted(set(inorder)))
        
    def inorder(self, root) -> list:
        if root is None:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)

두 번째 방법: 중간 순서는 이전 노드의 값이 현재 노드의 값보다 작은지 비교하기만 하면 되고 저장할 필요가 없다

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.prev = None
        return self.helper(root)
    
    def helper(self, root):
        if root is None:
            return True
        if not self.helper(root.left):
            return False
        if self.prev and self.prev.val >= root.val:
            return False
        self.prev = root
        return self.helper(root.right)

세 번째 방법: 각 노드의 왼쪽 아이의 값이 아버지 노드의 값보다 작은지, 오른쪽 아이의 값이 아버지 노드의 값보다 큰지 차례로 검증한다.

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        mini, maxi = float('-inf'), float('inf') 
        return self.isValid(root, mini, maxi)
    
    def isValid(self, root: TreeNode, mini: int, maxi: int) -> bool:
        if root is None:
            return True
        if mini >= root.val or maxi <= root.val:
            return False
        return self.isValid(root.left, mini, root.val) and self.isValid(root.right, root.val, maxi)

236. 이차나무의 최근 공공조상 Lowest Common Ancestor of a Binary Tree

LeetCodeCN 236번째 링크
우선 루트가 비어 있으면 루트를 되돌려주고, 루트가 p 또는 q라면 루트는 최근의 공공 조상이다.그리고 각각 좌자수와 우자수를 귀속시키고 결과를 보존한다. 양쪽을 모두 찾을 수 있다면 본 노드가 최근의 공공조상임을 증명하고 찾으면서 찾지 못하면 찾을 수 있는 쪽으로 계속 찾아간다.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None:
            return None
        if root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left or right:
            if left is None:
                return right
            elif right is None:
                return left
            else:
                return root
        else:
            return None

235. 두 갈래 수색 나무의 최근 공공 조상 Lowest Common Ancestor of a Binary Search Tree

LeetCodeCN 235번째 링크
첫 번째 방법: 위의 방법으로
두 번째 방법: 두 갈래로 나무를 검색하는 왼쪽 나무는 모두 아버지 노드보다 작고 오른쪽 나무는 아버지 노드보다 큰 특성을 이용하여 첫 번째 방법을 간소화할 수 있다

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root

세 번째 방법: 방법 2의 사고방식과 같이 귀속을 순환으로 바꾼다

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left
            elif p.val > root.val and q.val > root.val:
                root = root.right
            else:
                return root