力扣hot100_二叉树(4)_python版本

一、199. 二叉树的右视图

• 思路：
  直接复用层序遍历的代码，然后取每层的最后一个节点
• 代码：

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        '''
        层序遍历取每层的第一个
        '''
        if not root: return []

        res = []
        queue = collections.deque()
        queue.append(root)
        while queue:
            tmp_res = []
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp_res.append(node.val)
                if node.left:queue.append(node.left)
                if node.right:queue.append(node.right)
            res.append(tmp_res[-1])  # 只需要修改层序遍历的这里
        return res

二、114. 二叉树展开为链表

• 思路：
  直接复用先序遍历，然后遍历结果，依次修改结果就行
• 代码：

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        可以先序遍历节点，将节点放到列表中，然后连接上各节点
        """
        def dfs(cur):
            if not cur:
                return
            res.append(cur)
            dfs(cur.left)
            dfs(cur.right)
        res = []
        dfs(root)
        for idx, n in enumerate(res):
            if idx == len(res)-1:  
                n.left = None
                n.right = None
            else:
                n.left = None
                n.right = res[idx+1]

三、105. 从前序与中序遍历序列构造二叉树

• 思路：
  根据前中后序任意两个可以重建一颗二叉树，只靠前序和后序不是唯一的。
• 代码：

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:  # 空节点
            return None
        left_size = inorder.index(preorder[0])  # 左子树的大小
        left = self.buildTree(preorder[1: 1 + left_size], inorder[:left_size])
        right = self.buildTree(preorder[1 + left_size:], inorder[1 + left_size:])
        return TreeNode(preorder[0], left, right)

四、889. 根据前序和后序遍历构造二叉树

• 代码：

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not preorder:  # 空节点
            return None
        if len(preorder) == 1:  # 叶子节点
            return TreeNode(preorder[0])
        left_size = postorder.index(preorder[1]) + 1  # 左子树的大小
        left = self.constructFromPrePost(preorder[1: 1 + left_size], postorder[:left_size])
        right = self.constructFromPrePost(preorder[1 + left_size:], postorder[left_size: -1])
        return TreeNode(preorder[0], left, right)