[Leet Code] 나무 테마.

101. 대칭 두 갈래 나무

##1. 
class Solution:
    def isMirror(self,p1,p2):
        if not p1 and not p2:
            return True
        if not p1 or not p2:
            return False
        return self.isMirror(p1.left,p2.right) and self.isMirror(p1.right,p2.left) and p1.val==p2.val
            
    
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.isMirror(root.left,root.right)

##2. 
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        q=[root.left,root.right]
        while q:
            le=q.pop(0)
            ri=q.pop(0)
            if not le and not ri:
                continue #  true 
            if not le or not ri:
                return False
            if le.val!=ri.val:
                return False
            q.append(le.left)
            q.append(ri.right)
            q.append(le.right)
            q.append(ri.left)
        return True

#3. ， 

102. 두 갈래 나무의 차원 이동(BST)

#1. ， val， node
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
            if not root:
                return []
            ans=[]
            q=[root]
            while q:
                level_val=[]
                next_node=[]
                for item in q:
                    level_val.append(item.val)
                    if item.left:
                        next_node.append(item.left)
                    if item.right:
                        next_node.append(item.right)
                    q=next_node
                ans.append(level_val)
            return ans

#2. 
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
            if not root:
                return []
            ans=[]
            q=[root]
            while q:
                level_val=[]
                for _ in range(len(q)):
                    node=q.pop(0)
                    level_val.append(node.val)

                    if node.left:
                        q.append(node.left)
                    if node.right:
                        q.append(node.right)
                
                ans.append(level_val)
            return ans

104. 나무의 최대 깊이

#1.DFS 
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
#2.DFS 
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        s=[(1,root)]
        max_depth=0
        while s:
            cur_depth,node=s.pop()
            max_depth=max(cur_depth,max_depth)
            if node.left:
                s.append((cur_depth+1,node.left))
            if node.right:
                s.append((cur_depth+1,node.right))
        
        return max_depth
#3.BFS 
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
            if not root:
                return 0
            ans=[]
            q=[root]
            while q:
                level_val=[]
                for _ in range(len(q)):
                    node=q.pop(0)
                    level_val.append(node.val)
    
                    if node.left:
                        q.append(node.left)
                    if node.right:
                        q.append(node.right)
                
                ans.append(level_val)
            return len(ans)

105. 전차와 중차 역행 서열 구조 두 갈래 나무

##1. 
class Solution:
    # 
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder and not inorder:
            return None
        
        root=TreeNode(preorder[0])
        for i in range(len(inorder)):
            if inorder[i]==preorder[0]:
                
                left_inorder=inorder[:i]
                right_inorder=inorder[i+1:]
                
                left_preorder=preorder[1:1+i]
                right_preorder=preorder[1+i:]
                
                root.left=self.buildTree(left_preorder,left_inorder)
                root.right=self.buildTree(right_preorder,right_inorder)

        return root

144. 나무의 앞자리가 두루 다니다

##1. 
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ans=[]
        if not root:
            return []
        ans.append(root.val)
        ans+=self.preorderTraversal(root.left)
        ans+=self.preorderTraversal(root.right)
        
        return ans

## ， 
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ans=[]
        if not root:
            return ans
        s=[root]
        
        while s:
            node=s.pop(-1)
            ans.append(node.val)
            if node.right:
                s.append(node.right)
            if node.left:
                s.append(node.left)
        return ans

236. 이차나무의 최근 공공조상

#1. ，dfs ， true， ， 
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.ans=None
        def dfs(root):
            if not root:
                return False
            left=dfs(root.left)
            right=dfs(root.right)
            mid=root==p or root==q
            if mid+right+left>=2:
                self.ans=root
            return mid or left or right
        dfs(root)
        return self.ans
#2. dic 
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        dic={root:None}
        def bfs(root):
            if root:
                if root.left:
                    dic[root.left]=root
                if root.right:
                    dic[root.right]=root
                bfs(root.left)
                bfs(root.right)
        bfs(root)
        l1,l2=p,q
        while(l1!=l2):
            l1=dic.get(l1) if l1 else q
            l2=dic.get(l2) if l2 else p
        return l1