Leetcode. 1038(트리), 701(트리), 1008(트리), 814(트리), 105(트리)

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

inorder 로 탐색하는데 오른쪽 자식부터 탐색한다.

class Solution(object):
    def bstToGst(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def inorder(node, val):
            if not node: 
                return val
            node.val += inorder(node.right, val)
            return inorder(node.left, node.val)
        inorder(root, 0)
        return root

https://leetcode.com/problems/insert-into-a-binary-search-tree/

일반적인 이진 탐색 트리에 값 삽입하는 문제.

class Solution(object):
    def insertIntoBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if root == None:
            return TreeNode(val)
        p = root
        while p:
            if val < p.val:
                if p.left:
                    p = p.left
                else:
                    p.left = TreeNode(val)
                    break
            else:
                if p.right:
                    p = p.right
                else:
                    p.right = TreeNode(val)
                    break
        return root

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

전위 순회 값을 이용해서 이진 탐색 트리로 만드는건데 전위 순회가 루트부터 도므로 첫번째 인덱스 값은 루트이고, 그 뒤로 스택에 마지막에 들어있는 값보다 작은 값이 들어오면 왼쪽 자식, 아니면 오른쪽 자식인데 오른쪽 자식의 부모를 구해줄때 현재 값보다 더 큰값이 나올때까지 pop을 해주고 오른쪽 자식 값을 넣어줘야 제대로 오른쪽 자식이 들어간다.

class Solution(object):
    def bstFromPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: TreeNode
        """
        root = TreeNode(preorder[0])
        stack = [root]
        
        for node in preorder[1:]:
            if node < stack[-1].val:
                stack[-1].left = TreeNode(node)
                stack.append(stack[-1].left)
            else:
                while stack:
                    if stack[-1].val < node:
                        p = stack.pop()
                    else:
                        break
                p.right = TreeNode(node)
                stack.append(p.right)
        return root

https://leetcode.com/problems/binary-tree-pruning/

가지 치기 문제. 한번 방문했던 노드를 표시해줘야 다시 재방문을 안하게 되서 True, False flag로 표시를 해줬고,(checked변수) 만약 자식이 0이면서 리프 노드이면 자식을 가지치기해준다. 

class Solution(object):
    def pruneTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        
        stack = [[root, False]]
        while stack:
            p, checked = stack.pop()
            if not p:
                continue
            if p.left and (not p.left.left and not p.left.right and p.left.val == 0):
                p.left = None
            if p.right and (not p.right.left and not p.right.right and p.right.val == 0):
                p.right = None
            
            if not checked:
                stack.append([p, True])
                stack.append([p.left, False])
                stack.append([p.right, False])
        return root

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/

pre의 첫번째인자가 루트, 인오더에서 루트의 위치 왼쪽이 왼쪽 트리, 루트의 오른쪽부분이 오른쪽 트리이다.

class Solution(object):
    def buildTree(self, preorder, inorder):
        if not inorder:
            return
        root = TreeNode(preorder.pop(0))
        root.left = self.buildTree(preorder, inorder[:inorder.index(root.val)])
        root.right = self.buildTree(preorder, inorder[inorder.index(root.val) + 1:])
        return root