二叉树

博主：将夜
发布时间：2024 年 02 月 29 日
1009 次浏览
暂无评论
11421字数
预计阅读时长 ≈ 5分钟
分类：算法编程

## 定义

...

## 二叉树遍历

* 前序遍历: 按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。
* 中序遍历: 按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。
* 后序遍历: 类似于前序遍历, 按照左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。
* 层序遍历: 逐层遍历2叉树

因此, 名字前中后对应的是二叉树根节点的访问次序

代码实现如下

```python
# leetcode链接: https://leetcode.cn/problems/binary-tree-preorder-traversal/

# 基于 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-0288603975bbf2f001e48461b1458788571' 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-073fcc442c4ab07b67eba529a674384e532' 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-f1763395aa204988c9a11258cbc388b7203' 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)$的时间对根节点进行定位了。

```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-c3b353a129f9b1784836ef27ee683b60941' 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)

实践

题目: [将有序数组转换为二叉搜索树](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-e64fa691f723a8e5d55b0802467090da581' 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

最后修改：2024 年 03 月 05 日

本文作者: 将夜

本文标题: 二叉树

本文链接: https://zoe.red/2024/347.html

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

热门文章
随机文章

Lockon
可以尝试下用雷电4集线器，这样应该相当于任意两点直连，有点交换...
骄傲的匿名人士
测试邮箱表情: 今日诗词: 海上升明月, 天涯共此时!

二叉树

将夜 • 2024 年 02 月 29 日

## 定义

...

## 二叉树遍历

因此, 名字前中后对应的是二叉树根节点的访问次序

代码实现如下

```python
# leetcode链接: https://leetcode.cn/problems/binary-tree-preorder-traversal/

# 基于 collections.deque 双端队列
        from collections import deque
        # q = deque()
        q = []  # 从后出, 此时可以使用list代替deque

if elem.left is not None:
                q.append(elem.left)
  
        return results

</div><div role="tabpanel" id='tabs-0288603975bbf2f001e48461b1458788571' 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-073fcc442c4ab07b67eba529a674384e532' 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-f1763395aa204988c9a11258cbc388b7203' 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]

</div>
</div>
</div>

## 二叉树重建

已知中序遍历与前/后的遍历结果, 还原完整的二叉树或者给出另一种(后/前)遍历结果

*前序+中序重建思路(递归)*

对于任意一颗树而言，前序遍历的形式总是

```bash
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
```

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

```bash
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
```

![i前序+中序](https://zoe.red/usr/uploads/2024/03/2915956485.png)

*细节*

return myBuildTree(postorder, l_post, r_post, inorder, l_in, r_in, inoder_to_index_map)

```

</div><div role="tabpanel" id='tabs-c3b353a129f9b1784836ef27ee683b60941' class="tab-pane fade  ">

# 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

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)

*适用说明*

二分搜索树有着高效的插入、删除、查询操作。

*二分查找法过程图示*

* 1、等于所要查找的数据，直接找到
* 2、若小于 V，在小于 V 部分分组继续查询
* 2、若大于 V，在大于 V 部分分组继续查询

![二分查找法过程](https://zoe.red/usr/uploads/2024/03/3611946200.png)

实践

题目: [将有序数组转换为二叉搜索树](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/)

代码:

</div><div role="tabpanel" id='tabs-e64fa691f723a8e5d55b0802467090da581' class="tab-pane fade  ">

题目:[验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/)

描述: 给你一个二叉树的根节点 `root` ，判断其是否是一个有效的二叉搜索树。

代码:

if r_max is not None:
                    _max = max(_max, r_max)

return _min, _max

check(root)

return self.check_result
```

</div>
</div>
</div>

二叉树

相关推荐

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

PVE8.1下部署Intel集显虚拟化驱动

PVE8.1下-Ubuntu虚拟机创建与虚拟核显直通

此内容被密码保护

PVE8.1下软件源更新与其它配置

PVE8.1下-LXC容器创建与核显直通

直通卡-阵列卡区别

PVE8.1下部署Intel集显虚拟化驱动

PyTorch中nn.Linear()和nn.Embedding()的区别

SSH端口转发实战

Transformer实战-1序列拷贝

二叉树

相关推荐

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

二叉树

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款