leetcode_binary_tree_series
Tim Chen(motion$) Lv5
  2020-03-09 16:55:53 2020-03-09 16:55   2023-07-22 10:19:30      1.1k 字  4 分钟  

什么是树

  • **树(Tree)**是一种非线性结构，用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。树是递归结构，在树的定义中又用到了树的概念。

什么是二叉树

  • **二叉树(Binary tree)**是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或者“右子树”。二叉树的分支具有左右次序，不能随意颠倒。二叉树可以为空。

完全二叉树

  • 若设二叉树的深度为ℎ，除第ℎ层外，其它各层(1～ℎ−1)的结点数都达到最大个数，第ℎ层所有的结点都连续集中在最左边，这就是完全二叉树

什么是二叉搜索树

  • 左子树的值都比根节点小，右子树的值都比根节点大。

树的定义(Python)

1
2
3
4
5
6
# Definition for a binary tree node.
class TreeNode:
	def __init__(self, x):
		self.value = x
		self.left = None
		self.right = None

树的遍历

深度优先，通常有前序(pre-order)，中序(in-order)，后序(post-order)3种遍历方法，每一种又分递归和迭代两种实现

  • 3种遍历经过的路径都是一样的，而且每个节点都会被访问3次，当我们在第一次访问该节点就打印出来的话，那么这就是前序；当我们第二次访问该节点才打印出来的话，那么这就是中序；当我们第三次访问该节点才打印出来的话，那么这就是后序。
  • 伪代码，递归实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # pseudocode，递归
    ## 前序
    func preorder(root):
    	if not root: return
    	**print(root.val)**
    	preorder(root.left)
    	preorder(root.right)
    	

    ## 中序, 对于二叉搜索树，中序后的是一个排序数组
    func inorder(root):
    	if not root: return
    	inorder(root.left)
    	**print(root.val)**
    	inorder(root.right)
    	
    ## 后序
    func postorder(root):
    	if not root: return
    	postorder(root.left)
    	postorder(root.right)
    	**print(root.val)**
  • Python 实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    ## 前序遍历
    ### 1. 递归实现
    class Solution:
    	def preorderTraversal(self, root: TreeNode) -> List[int]:
    		ans = []
    		if not root: return ans
    		self.preTraversal(root, ans)
    		return ans
    		
    	def preTraversal(self, t, ans):
    		ans.append(t.val)
    		if t.left:
    			self.preTraversal(t.left, ans)
    		if t.right:
    			self.preTraversal(t.right, ans)
    			
    ### 2. 迭代实现，栈
    class Solution:
    	def preorderTraversal(self, root: TreeNode) -> List[int]:
    		ans = []
    		stack = []
    		if not root:
    			return ans
    		p = root
    		while(p or len(stack)):
    			if p:
    				ans.append(p.val)
    				stack.append(p)
    				p = p.left
    			else:
    				p = stack[-1]
    				stack.pop(-1)
    				p = p.right
    		return ans
    		
    ## ---------------split line-------------------

    ## 中序序遍历
    ### 1. 递归实现
    class Solution:
    	def inorderTraversal(self, root: TreeNode) -> List[int]:
    		ans = []
    		if not root: return ans
    		self.inTraversal(root, ans)
    		return ans
    		
    	def inTraversal(self, t, ans):
    		ans.append(t.val)
    		if t.left:
    			self.inTraversal(t.left, ans)
    		if t.right:
    			self.inTraversal(t.right, ans)
    			
    ### 2. 迭代实现
    class Solution:
    	def inorderTraversal(self, root: TreeNode) -> List[int]:
    		ans = []
    		stack = []
    		if not root:
    			return ans
    		p = root
    		while(p or len(stack)):
    			if p:
    				stack.append(p)
    				p = p.left
    			else:
    				p = stack[-1]
    				ans.append(p.val)
    				stack.pop(-1)
    				p = p.right
    		return ans
    		
    ## ---------------split line-------------------

    ## 后序序遍历
    ### 1. 递归实现
    class Solution:
    	def postorderTraversal(self, root: TreeNode) -> List[int]:
    		ans = []
    		if not root: return ans
    		self.postTraversal(root, ans)
    		return ans
    		
    	def postTraversal(self, t, ans):
    		ans.append(t.val)
    		if t.left:
    			self.postTraversal(t.left, ans)
    		if t.right:
    			self.postTraversal(t.right, ans)
    	
    ### 2. 迭代实现，因为前序是root->left->right, 而后序是left->right->root，刚好反过来
    class Solution:
    	def postorderTraversal(self, root: TreeNode) -> List[int]:
    		ans = []
    		stack = []
    		if not root:
    			return ans
    		p = root
    		while(p or len(stack)):
    			if p:
    				ans.append(p.val)
    				stack.append(p)
    				p = p.right
    			else:
    				p = stack[-1]
    				stack.pop(-1)
    				p = p.left
    		return [val for val in reversed(ans)]

广度优先

  • 层次遍历(level-order)
  • 利用队列(queue)来实现
      1. 根节点先入队列
      1. 迭代当前队列上的所有元素
      1. 若该元素所指节点的左右孩子节点非空，则将其左右孩子的指针入队列，把当前元素出队列，并保存其数值到结果数组中。
      1. 循环重复2-4，直到队列为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
	def levelOrder(self, root: TreeNode) -> List[List[int]]:
		queue = [root]
		res = []
		if not root:
			return []
		while queue:
			templist = []
			templen = len(queue)
			for i in range(templen):
				temp = queue.pop(0)
				templist.append(temp.val)
				if temp.left:
					queue.append(temp.left)
				if temp.right:
					queue.append(temp.right)
			res.append(templist)
		return res

链表(Linked list)，树(Tree)，图(Graph)的关系

  • 链表是特殊的树，树是特殊的图。

reference-参考

  • 本文标题：leetcode_binary_tree_series
  • 本文作者：Tim Chen(motion$)
  • 创建时间：2020-03-09 16:55:53
  • 本文链接：2020/03/09/alogrithms/leetcode-binary-tree-series/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论
  1. 1. 什么是树
  2. 2. 什么是二叉树
  3. 3. 完全二叉树
  4. 4. 什么是二叉搜索树
  5. 5. 树的定义(Python)
  6. 6. 树的遍历
    1. 6.1. 深度优先，通常有前序(pre-order)，中序(in-order)，后序(post-order)3种遍历方法，每一种又分递归和迭代两种实现
    2. 6.2. 广度优先
    3. 6.3. 链表(Linked list)，树(Tree)，图(Graph)的关系
  7. 7. reference-参考