题解 | 输出二叉树的右视图-- leetcode 105 --leetcode 297

#


# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求二叉树的右视图
# @param preOrder int整型一维数组 先序遍历
# @param inOrder int整型一维数组 中序遍历
# @return int整型一维数组
#

"""
参考力扣 leetcode105官方视频： 
 1. 前序比遍历的第一个节点是是根节点
   前序遍历：
   [根] [左子树根 --左子树] [右子树根 ---右子树]
   设 前序开始位置preleft  结束位置为preright
   []
 2. 中序遍历
   [左子树]  [根] [ 右子树]
   设中序的起始位置inleft 中序结束位置 inright
 3. 在中序从左到右遍历找到根节点位置 inorder_root位置  ----可以提前用哈希表存储中序中的
 中序 ：[inorder_left ...inorder_root-1] [inorder_root] [inderer_root+1....inorder_right ]
 4 前序中右子树的根位置怎么找？ 
  preorder_left  [preorder_left+1.......x][x+1 ........preorder_right]

  可以利用前序中左子树长度等于 中序左子树长度
     [preorder_left+1.......x] =[inorder_left ...inorder_root-1]

     x-(preorder_left+1 )=inorder_root-1-inorder_left 
     得到x =inorder_root-inorder_left+preorder_left
     所以在前序中右子树的开始位置为x+1 : inorder_root-inorder_left+preorder_left+1

  5. 递归结束条件 preorder_left>preright


"""
class Solution:

    # 使用BM40方法建树
    # 层序遍历 取右端点
    def solve(self , preOrder: List[int], inOrder: List[int]) -> List[int]:
        # write code here
        # 建立一个map 保存中序遍历的所有节点 方便查找root 节点
        map=dict()
        for i in  range(len(inOrder)):
            map[inOrder[i]]=i
        #print(map)
        def buildtree(preOrder,preorder_left,preorder_right,inOrder,inorder_left,inorder_right):
            # 递归结束条件
            if preorder_left>preorder_right:
                return 
            # 取出前序遍历的第一个元素为根节点
            preorder_root =preorder_left
            # c创建 root 
            
            root =TreeNode(preOrder[preorder_root])
            # map中找root 节点的位置
            inoreder_root=map[preOrder[preorder_root]]
            #print("root",root.val)
            #print("inorde root",inoreder_root,preorder_left)
            # 递归左子树
                              #前序
            root.left =buildtree(preOrder,preorder_left+1,inoreder_root-inorder_left+preorder_left,inOrder,inorder_left,inoreder_root-1)
            # 递归右子树
            root.right =buildtree(preOrder,inoreder_root-inorder_left+preorder_left+1,preorder_right,inOrder,inoreder_root+1,inorder_right)
            return  root 

        res=[]
        import collections
        def dfs(root):
            if not root:
                return
            dq=collections.deque()
            dq.append(root)

            while dq: 
                vals=[] # 每层的值
                # 一层的父节点的个数
                n=len(dq)
                print("dq",len(dq))
                for i in range(n):
                    node =dq.popleft()
                    vals.append(node.val )
                    if node.left:
                        dq.append(node.left)
                    if node.right:
                        dq.append(node.right)
                res.append(vals)
        root =buildtree(preOrder,0,len(preOrder)-1,inOrder,0,len(inOrder)-1)
        dfs(root)
        print(res)
        ret=[]
        for level in res :
            ret.append(level[-1])
        return ret