1、二叉树___总结

2024-01-03 18:59:10

目录
一、树的构造
二、树的搜索（二叉搜索树）

广度搜索
深度搜索

三、二叉树的遍历（二叉排序树）

前序遍历
中序遍历
后序遍历
层序遍历

四、二叉树的深度

最小深度
最大深度

------------------------------------------------------搜索-------------------------------------------------------

------------------------------------------------------递归-------------------------------------------------------

原创：https://www.cnblogs.com/bigsai/p/11393609.html

前序遍历

根结点 ---> 左子树 ---> 右子树

中序遍历

左子树---> 根结点 ---> 右子树

后序遍历

子树 ---> 右子树 ---> 根结点

层序遍历

按层遍历，左右节点应该均衡考虑

选用队列来实现

------------------------------------------------------非递归-------------------------------------------------------

------------------------------------------------------深度-------------------------------------------------------

原创：https://blog.csdn.net/melon0014/article/details/86579813

二叉树的最小深度

1. 二叉树的最小深度

#111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

 

示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
 

提示：

树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000

目标：找最小的叶子节点
（1）BFS

 1 def generate_related_nodes(visited, node):
 2     next_node_list = []
 3     for next_node in [node[0].left, node[0].right]:
 4         if next_node and next_node not in visited:
 5             next_node_list.append([next_node, node[1]+1])
 6     return next_node_list
 7 
 8 class Solution(object):
 9     def minDepth(self, root):
10         """
11         :type root: TreeNode
12         :rtype: int
13         """
14         if not root: return 0
15         visited = {}
16         level = 1
17         queue = []
18         visited[root] = 1
19         queue.append([root, level])
20         while queue:
21             node = queue.pop(0)
22             if not node[0].left and not node[0].right:
23                 return node[1]
24             queue.extend(generate_related_nodes(visited, node))

View Code

（2）DFS
要记录深度level，更新max和min

 1 import sys
 2 
 3 class Solution(object):
 4     def __init__(self):
 5         self.min_depth = sys.maxint
 6 
 7     def minDepth(self, root):
 8         if not root:
 9             return 0
10         self.DFS(1, root)
11         return self.min_depth
12         
13     def DFS(self, depth, root):
14         if not root.left and not root.right:
15             if depth < self.min_depth:
16                 self.min_depth = depth
17         if root.left:
18             self.DFS(depth + 1, root.left)
19         if root.right:
20             self.DFS(depth + 1, root.right)

View Code

二叉树的最大深度

#Leetcode 104

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   /   9  20
    /     15   7
返回它的最大深度 3 。

（1）DFS
*时间复杂度O（N）

 1 class Solution(object):
 2     def __init__(self):
 3         self.max_depth = 0
 4 
 5     def maxDepth(self, root):
 6         if not root:
 7             return 0
 8         self.DFS(1, root)
 9         return self.max_depth
10 
11     def DFS(self, depth, root):
12         if depth > self.max_depth:
13             self.max_depth = depth
14         if root.left:
15             self.DFS(depth + 1, root.left)
16         if root.right:
17             self.DFS(depth + 1, root.right)

View Code

（2）BFS
*时间复杂度O（N）

 1 class Solution(object):
 2     def __init__(self):
 3         self.max_depth = 0
 4 
 5     def maxDepth(self, root):
 6         if not root:
 7             return 0
 8         self.BFS(root)
 9         return self.max_depth
10 
11     def BFS(self, root):
12         queue = [root]
13         while queue:
14             size = len(queue)
15             self.max_depth += 1
16             for _ in range(size):
17                 cur_node = queue.pop(0)
18                 if cur_node.left:
19                     queue.append(cur_node.left)
20                 if cur_node.right:
21                     queue.append(cur_node.right)

View Code

1、二叉树___总结

码农公寓

二叉树的最小深度

二叉树的最大深度

相关文章