【Leetcode】105: 从前序与中序遍历序列构造二叉树
2023-09-11 14:21:08 时间
这题目是有一个常见的套路的,由于先序遍历的结果list都会遵循这样的一个排列方式,也就是第一个是root,后面的分别是左子树的node的集合,以及右子树的node的集合。
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
而inorder中序遍历的结果则是:
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
画成下图就可以表示为:
我们通过preorder拿到root的地址之后,就可以找到root在inorder当中的位置。然后拿到preorder和inorder当中的左子树和右子树,这样就可以对root.left以及root.right进行递归,build出一棵完整的二叉树。
代码如下:
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: if not preorder or not inorder: # 递归终止条件,用这个终止条件是因为如果为空,则后面的递归(用分治法的时候)无法进行对list的切片 return root = TreeNode(preorder[0]) idx = inorder.index(preorder[0]) root.left = self.buildTree(preorder[1:1 + idx], inorder[:idx]) root.right = self.buildTree(preorder[1 + idx:], inorder[idx + 1:]) return root
相关文章
- Leetcode: Largest Divisible Subset
- Leetcode: Intersection of Two Arrays
- Leetcode: Pascal's Triangle II
- Leetcode: Length of Last Word
- LeetCode高频题:二叉树的锯齿形(Z字形,之字形)层序遍历
- 【Leetcode】102. 二叉树的层序遍历(中等)
- 【LeetCode】二叉树的遍历与构建问题
- [LeetCode]剑指 Offer 50. 第一个只出现一次的字符
- LeetCode 94. 二叉树的中序遍历
- LeetCode 22. 括号生成
- 92、【树与二叉树】leetcode ——111. 二叉树的最小深度:层次遍历+先序DFS+后序DFS[子问题分解](C++版本)
- 89、【树与二叉树】leetcode ——101. 对称二叉树:后序递归+迭代法+层次遍历(C++版本)
- 67、【哈希表】leetcode——242. 有效的字母异位词(C++版本)
- 【LeetCode】242. Valid Anagram (2 solutions)
- 【LeetCode】230. Kth Smallest Element in a BST (2 solutions)
- 【leetcode】103:二叉树的锯齿形层序遍历
- 【leetcode】102:二叉树的层序遍历
- [LeetCode] 1143. Longest Common Subsequence 最长公共子序列
- [LeetCode] 589. N-ary Tree Postorder Traversal N叉树的后序遍历
- [LeetCode] N-ary Tree Level Order Traversal N叉树层序遍历
- [LeetCode] Relative Ranks 相对排名
- [LeetCode] 40. Combination Sum II 组合之和之二
- [LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 由先序和中序遍历建立二叉树
- leetcode 145. Binary Tree Postorder Traversal 二叉树的后序遍历 (中等)
- leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树(中等)
- leetcode 300. Longest Increasing Subsequence 最长递增子序列 (中等)
- leetcode算法145.二叉树的后序遍历
- leetcode算法20.有效的括号