Loading... ## 定义 ... ## 二叉树遍历 * 前序遍历: 按照访问根节点——左子树——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。 * 中序遍历: 按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。 * 后序遍历: 类似于前序遍历, 按照左子树——右子树——根节点的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。 * 层序遍历: 逐层遍历2叉树 因此, 名字前中后对应的是二叉树根节点的访问次序 代码实现如下 <div class="tab-container post_tab box-shadow-wrap-lg"> <ul class="nav no-padder b-b scroll-hide" role="tablist"> <li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" aria-controls='tabs-fe8f3422972c6aa28a71fe465a20ed6770' role="tab" data-target='#tabs-fe8f3422972c6aa28a71fe465a20ed6770'>前序遍历</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" aria-controls='tabs-65642a2bf51dd44f7b76be42dfeb8bc2221' role="tab" data-target='#tabs-65642a2bf51dd44f7b76be42dfeb8bc2221'>中序遍历</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" aria-controls='tabs-5a618c2b64eb848bc70591733b467342692' role="tab" data-target='#tabs-5a618c2b64eb848bc70591733b467342692'>后序遍历</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" aria-controls='tabs-c4d038e538f81beef7c4e39274a26a40323' role="tab" data-target='#tabs-c4d038e538f81beef7c4e39274a26a40323'>层序遍历</a></li> </ul> <div class="tab-content no-border"> <div role="tabpanel" id='tabs-fe8f3422972c6aa28a71fe465a20ed6770' class="tab-pane fade active in"> ```python # leetcode链接: https://leetcode.cn/problems/binary-tree-preorder-traversal/ # 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if root is None: return [] # 基于 collections.deque 双端队列 from collections import deque # q = deque() q = [] # 从后出, 此时可以使用list代替deque q.append(root) results = [] while q: # 从前出 # elem = q.popleft() # results += [elem.val] # # 注意顺序以及从队列左侧加入 # if elem.right is not None: # q.appendleft(elem.right) # if elem.left is not None: # q.appendleft(elem.left) # 从后出, 此时可以使用list代替deque elem = q.pop() results += [elem.val] # 注意顺序以及从队列左侧加入 if elem.right is not None: q.append(elem.right) if elem.left is not None: q.append(elem.left) return results # 递归方法 # 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def digui(node): if node is None: return [] return [node.val] + digui(node.left) + digui(node.right) return digui(root) ``` </div><div role="tabpanel" id='tabs-65642a2bf51dd44f7b76be42dfeb8bc2221' class="tab-pane fade "> ```python # leetcode链接: https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/506045860/ # 递归方法 # 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def digui(node): if node is None: return [] return digui(node.left) + [node.val] + digui(node.right) return digui(root) ``` </div><div role="tabpanel" id='tabs-5a618c2b64eb848bc70591733b467342692' class="tab-pane fade "> ```python # leetcode链接: https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/506050563/ # 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def digui(node): if node is None: return [] return digui(node.left) + digui(node.right) + [node.val] return digui(root) ``` </div><div role="tabpanel" id='tabs-c4d038e538f81beef7c4e39274a26a40323' class="tab-pane fade "> ```python # leetcode链接: https://leetcode.cn/problems/binary-tree-level-order-traversal/?envType=study-plan-v2&envId=top-interview-150 # 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: def digui(node_list): next_layer_node_list = [] layer_results = [] # 注意: node 不能为None for node in node_list: layer_results += [node.val] if node.left is not None: next_layer_node_list += [node.left] if node.right is not None: next_layer_node_list += [node.right] # 递归出口 if len(next_layer_node_list) == 0: return [layer_results] else: return layer_results, * digui(next_layer_node_list) if root is None: return [] return digui([root]) ``` </div> </div> </div> ## 二叉树重建 已知中序遍历与前/后的遍历结果, 还原完整的二叉树或者给出另一种(后/前)遍历结果 *前序+中序重建思路(递归)* 对于任意一颗树而言,前序遍历的形式总是 ```bash [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ] ``` 即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是 ```bash [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ] ``` 只要我们在中序遍历中定位到根节点,那么我们就可以分别知道**左子树和右子树中的节点数目**。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此我们就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位。 这样以来,我们就知道了左子树的前序遍历和中序遍历结果,以及右子树的前序遍历和中序遍历结果,我们就可以递归地对构造出左子树和右子树,再将这两颗子树接到根节点的左右位置。 ![i前序+中序](https://zoe.red/usr/uploads/2024/03/2915956485.png) *细节* 在中序遍历中对根节点进行定位时,一种简单的方法是直接扫描整个中序遍历的结果并找出根节点,但这样做的时间复杂度较高。我们可以考虑**使用哈希表来帮助我们快速地定位根节点**。对于哈希映射中的每个键值对,键表示一个元素(节点的值),值表示其在中序遍历中的出现位置。在构造二叉树的过程之前,我们可以对中序遍历的列表进行一遍扫描,就可以构造出这个哈希映射。在此后构造二叉树的过程中,我们就只需要 $O(1)$的时间对根节点进行定位了。 <div class="tab-container post_tab box-shadow-wrap-lg"> <ul class="nav no-padder b-b scroll-hide" role="tablist"> <li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" aria-controls='tabs-09a61cd167f217dc9a22a357eda332e9980' role="tab" data-target='#tabs-09a61cd167f217dc9a22a357eda332e9980'>中序+后续: 重建Tree</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" aria-controls='tabs-2ab675eca4c1d081e9185266458aa519871' role="tab" data-target='#tabs-2ab675eca4c1d081e9185266458aa519871'>前序+中序: 重建</a></li> </ul> <div class="tab-content no-border"> <div role="tabpanel" id='tabs-09a61cd167f217dc9a22a357eda332e9980' class="tab-pane fade active in"> ```python # Leetcode链接: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150 # 题目: 从中序与后序遍历序列构造二叉树 # 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 def myBuildTree(postorder, l_post, r_post, inorder, l_in, r_in, inoder_to_index_map): if l_post > r_post: return None # 后续遍历, 最后一个节点为根 val = postorder[r_post] root_node = TreeNode(val) root_index_in_inoder = inoder_to_index_map[val] left_sub_tree_size = root_index_in_inoder - l_in root_node.left = myBuildTree(postorder, l_post, l_post + left_sub_tree_size -1, inorder, l_in, root_index_in_inoder-1, inoder_to_index_map) root_node.right = myBuildTree(postorder, l_post + left_sub_tree_size, r_post -1, inorder, root_index_in_inoder+1, r_in, inoder_to_index_map) return root_node class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: if len(inorder) == 0: return None inoder_to_index_map = {node: i for i, node in enumerate(inorder)} l_in, r_in = 0, len(inorder)-1 l_post, r_post = 0, len(postorder) -1 return myBuildTree(postorder, l_post, r_post, inorder, l_in, r_in, inoder_to_index_map) ``` </div><div role="tabpanel" id='tabs-2ab675eca4c1d081e9185266458aa519871' class="tab-pane fade "> ```python # 题目: 从前序与中序遍历序列构造二叉树 # Leetcode链接: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150 # 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 def myBuildTree(preorder, l_pre, r_pre, inorder, l_in, r_in, inoder_to_index_map): if l_pre > r_pre: return None # 前序遍历的第一个是根节点 val = preorder[l_pre] root_node = TreeNode(val) root_index_in_inoder = inoder_to_index_map[val] # 对应中序中的位置 left_sub_tree_size = root_index_in_inoder - l_in # 左子树节点数 root_node.left = myBuildTree(preorder, l_pre+1, l_pre+left_sub_tree_size, inorder, l_in, root_index_in_inoder-1, inoder_to_index_map) root_node.right = myBuildTree(preorder, l_pre+left_sub_tree_size+1, r_pre, inorder, root_index_in_inoder+1, r_in, inoder_to_index_map) return root_node class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder: return None inoder_to_index_map = {node: index for index, node in enumerate(inorder)} # l_in, r_in = 0, len(inorder) - 1 l_pre, r_pre = 0, len(preorder) - 1 return myBuildTree(preorder, l_pre, r_pre, inorder, l_in, r_in, inoder_to_index_map) ``` </div> </div> </div> ## 二分搜索树 二分搜索树(英语:Binary Search Tree),也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件: * 若它的左子树不为空,左子树上所有节点的值都小于它的根节点。 * 若它的右子树不为空,右子树上所有的节点的值都大于它的根节点。 它的左、右子树也都是二分搜索树。 如下图所示: ![二分搜索树](https://zoe.red/usr/uploads/2024/03/537773175.png) *适用说明* 二分搜索树有着高效的插入、删除、查询操作。 平均时间的时间复杂度为 $O(log n)$,最差情况为 $O(n)$。**二分搜索树与堆不同,不一定是完全二叉树**,底层不容易直接用数组表示故采用链表来实现二分搜索树。 *二分查找法过程图示* 二分查找法的思想在 1946 年提出,查找问题是计算机中非常重要的基础问题,对于有序数列,才能使用二分查找法。如果我们要查找一元素,先看数组中间的值V和所需查找数据的大小关系,分三种情况: * 1、等于所要查找的数据,直接找到 * 2、若小于 V,在小于 V 部分分组继续查询 * 2、若大于 V,在大于 V 部分分组继续查询 ![二分查找法过程](https://zoe.red/usr/uploads/2024/03/3611946200.png) 实践 <div class="tab-container post_tab box-shadow-wrap-lg"> <ul class="nav no-padder b-b scroll-hide" role="tablist"> <li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" aria-controls='tabs-87c9a9cdb0368762d939f9da9716af1c370' role="tab" data-target='#tabs-87c9a9cdb0368762d939f9da9716af1c370'>建立二叉搜索树</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" aria-controls='tabs-bf8b77ead3ccb1e95a8396412484460c211' role="tab" data-target='#tabs-bf8b77ead3ccb1e95a8396412484460c211'>判断是否为二叉搜索树</a></li> </ul> <div class="tab-content no-border"> <div role="tabpanel" id='tabs-87c9a9cdb0368762d939f9da9716af1c370' class="tab-pane fade active in"> 题目: [将有序数组转换为二叉搜索树](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/) 描述: 给你一个整数数组 `nums` ,其中元素已经按 **升序** 排列,请你将其转换为一棵 **高度平衡** 二叉搜索树。**高度平衡** 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 代码: ```python # 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 def buildTree(node_list, l, r): # 每次取目标区间的中间作为新增子节点 if l > r: return None m = (l+r)//2 val = node_list[m] root = TreeNode(val) root.left = buildTree(node_list, l, m-1) root.right = buildTree(node_list, m+1, r) return root class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: # if not nums: # return None l, r = 0, len(nums)-1 return buildTree(nums, l, r) ``` </div><div role="tabpanel" id='tabs-bf8b77ead3ccb1e95a8396412484460c211' class="tab-pane fade "> 题目:[验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/) 描述: 给你一个二叉树的根节点 `root` ,判断其是否是一个有效的二叉搜索树。 代码: ```python # 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 __init__(self): self.check_result = True def isValidBST(self, root: Optional[TreeNode]) -> bool: def check(node): if node is None: return None, None # if node.left is None and node.right is None: # return None, None _min = node.val _max = node.val if node.left is not None: # 基本判断1: 与直接的左右节点关系 if node.left.val >= node.val: self.check_result = False # 基本判断2: 与子树对应的最大最小值关系 l_min, l_max = check(node.left) if l_max is not None and l_max >= node.val: self.check_result = False # if l_min is not None and l_min >= node.val: # self.check_result = False # 返回值: 作为子树的最小最大值 if l_min is not None: _min = min(_min, l_min) if node.right is not None: if node.right.val <= node.val: self.check_result = False r_min, r_max = check(node.right) if r_min is not None and r_min <= node.val: self.check_result = False # if r_max is not None and r_max <= node.val: # self.check_result = False if r_max is not None: _max = max(_max, r_max) return _min, _max check(root) return self.check_result ``` </div> </div> </div> THE END 本文作者:将夜 本文链接:https://zoe.red/2024/347.html 版权声明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。 最后修改:2024 年 03 月 05 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏