js怎么取到遍历中的特定值_LeetCode 1028 hard 从先序遍历还原二叉树 Python解题记录...

我们在该专栏中记录了我俩的刷题记录。

我们更新的所有题目都在目录中。

今天的题目是

力扣​leetcode-cn.com

题目

We run a preorder depth first search on the root of a binary tree.At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. (If the depth of a node is D, the depth of its immediate child is D+1. The depth of the root node is 0.)If a node has only one child, that child is guaranteed to be the left child.Given the output S of this traversal, recover the tree and return its root.我们从二叉树的根节点 root 开始进行深度优先搜索。在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。如果节点只有一个子节点，那么保证该子节点为左子节点。给出遍历输出 S，还原树并返回其根节点 root。Example 1

Input: "1-2--3--4-5--6--7"Output: [1,2,5,3,4,6,7]Example 2:

Input: "1-2--3---4-5--6---7"Output: [1,2,5,3,null,6,null,4,null,7]Example 3:

Input: "1-401--349---90--88"Output: [1,401,null,349,88,90]

思路 - DFS先序遍历

这道题给的是先序遍历的序列，那我们照着先序遍历，使用一个辅助栈，把树还原即可
在先序遍历的过程中，如果不断往下走，就不断入栈，如果是往上走，就是出栈
注意，题目条件中说了，如果结点只有一个子节点，保证该子节点是左子节点。那么我们可以在建树的时候，直接判断当前结点的左子结点是否存在，不存在就加入到左子节点，存在就加入到右子节点
我们举个例子直观的说明一下

例如： 输入："1-2--3--4-5" 输出：[1,2,5,3,4,6,7]树：stack = [] input = "1-2--3--4-5" 首先把1取出来，作为整个树的root，并入栈树：1 stack = [1] input = "-2--3--4-5" 把2取出来，以及2的depth为1 (depth为2前面的-的个数) 由于depth = len(stack)，说明还是往下走，取到栈顶1(不出栈)，且1的左子树不存在，直接把2接到1的左子树，同时2入栈树：1/2 stack = [1,2] input = "--3--4-5" 把3取出来，以及3的depth为2 由于depth = len(stack)，说明还是往下走，取到栈顶2(不出栈)，且2的左子树不存来，直接把3接到2的左子树，同时3入栈树：1/2/3 stack = [1,2,3] input = "--4-5" 把3取出来，以及3的depth为2 由于depth < len(stack)，说明往上走了，不断出栈，使得depth = len(stack)，(这样保证栈顶是3的父节点)，出栈后，stack=[1,2]，得到栈顶2 (不出栈)，2的左子树存在，所以把4接到2的右子树，同时4入栈树：1/2/ 3 4 stack = [1,2,4] input = "-5" 把5取出来，以及5的depth为1 由于depth < len(stack)，说明继续往上走，不断出栈，使得depth=len(stack)，stack=[1]，得到栈顶1 (不出栈)，1的左子树存在，所以把5接到1的右子树，5入栈树：1/ 2 5/ 3 4

所以整个过程中，我们需要维护一个栈，同时需要写两个辅助函数去找当前的结点值是多少，以及当前的结点深度是多少
我们来看代码

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def recoverFromPreorder(self, S: str) -> TreeNode:# 第一个辅助函数，给定起始点的index，找结点值def detectNum(start):ret = 0while start < len(S) and "0" <= S[start] <= "9":ret = ret * 10 + int(S[start])start += 1# 返回结点值，以及下一个起始点的indexreturn ret, start# 第二个辅助函数，给定起始点的index，找结点的深度def detectDepth(start):ret = 0while start < len(S) and S[start] == "-":ret += 1start += 1# 返回深度，以及下一个起始点的indexreturn ret, start if not S:return None# 找根结点的结点值val, idx = detectNum(0)# 结构化根结点root = TreeNode(val)# 根结点入栈stack = [root]while idx < len(S):# 检测当前结点的深度depth, idx = detectDepth(idx)# 检测当前结点的结点值val, idx = detectNum(idx)# 如果深度小于栈的深度，不断出栈，使得二者深度相等# 这样使得栈顶元素是当前结点的父结点while depth < len(stack):stack.pop()# 把父节点取出来parent = stack[-1]node = TreeNode(val)# 如果父节点无左子树，则放到左子树上# 反之，放到右子树上if not parent.left:parent.left = nodeelse:parent.right = node# 当前点入栈stack.append(node)return root

总结

以上是生活随笔为你收集整理的js怎么取到遍历中的特定值_LeetCode 1028 hard 从先序遍历还原二叉树 Python解题记录...的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。