【leetcode】1028.从先序遍历还原二叉树（python实现）

深碍√TFBOYSˉ_ 2022-11-01 13:56 12阅读 0赞

题目：

我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出 S，还原树并返回其根节点 root。

示例 1：

![fac7ead2b4aaa7e3312cc7ec1ff0e9e7.png][]

输入："1-2--3--4-5--6--7"  
输出：\[1,2,5,3,4,6,7\]

没做出来，直接理解官方答案

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def recoverFromPreorder(self, S: str) -> TreeNode:
            pos,path=0,list()#path存储了从根节点到当前节点路径上的所有节点
            while pos < len(S):
                level = 0
                while S[pos] == "-":
                    level += 1
                    pos += 1
                value = 0
                while pos<len(S) and S[pos].isdigit():#判断字符串是否只包含数字
                    value = 10*value+int(S[pos])
                    pos += 1
                node = TreeNode(value)
                if len(path) == level:#判断路径中最后一个节点是否在新节点的上一层
                    if path:
                        path[-1].left = node
                else:
                    path = path[:level]#回溯到对应节点上一层的节点（:后面的数字属于开区间）
                    path[-1].right = node
                path.append(node)#在路径中加入新的节点
            return path[0]

[fac7ead2b4aaa7e3312cc7ec1ff0e9e7.png]: /images/20221024/0316e512fab8472b8a58425240fcb90e.png