树

Retrospect

基本概念

树

  • 节点的度数为节点的孩子个数(和图不一样,出度和入度都是节点的度数)
  • 树的节点数等于所有节点的度数和+1(二叉树的节点个数可以直接推算出来的(考试当场演算-ps:5语))
  • 树根为第一层(学计算机的都知道万物是从0开始的(狗头) - 跟常识相违背啊)
  • 度为m的树第i层最多有mi-1个节点

二叉树

  • n0=n2+1
  • 第i层最多有2i-1个节点
  • h层二叉树最多有2h-1个节点

暂时就说这么多吧,都是应付考试的东西,讲真全靠记忆.

树的遍历Traversal

树的遍历分为先序遍历,中序遍历,后序遍历

口述一下三种方式的特征吧:

  • 先序遍历(根 - 左 - 右)
  • 中序遍历(左 - 根 - 右)
  • 后序遍历(左 - 右 - 根)

例如:

pCrwUqe.png

  • 先序序列：ABDEGHCF；
  • 中序序列：DBGEHACF；
  • 后序序列：DGHEBFCA。
  • 补充：二叉树也称为二分树，它是树形结构的一种，其特点是每个结点至多有二棵子树，并且二叉树的子树有左右
    之分，其次序不能任意颠倒。二叉树的遍历序列按照访问根节点的顺序分为先序（先访问根节点，接下来先序访问
    左子树，再先序访问右子树）、中序（先中序访问左子树，然后访问根节点，最后中序访问右子树）和后序（先后
    序访问左子树，再后序访问右子树，最后访问根节点）。如果知道一棵二叉树的先序和中序序列或者中序和后序序
    列，那么也可以还原出该二叉树。

剑指offer

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]

理解Code

这个题目不是到是伪代码还是什么,反正运行的时候总是报错.还是学习一下思想吧:

  • 首先判断根节点(如果为空)就返回空列表
  • res列表用于存放返回的结果,tmp用于存放每一层的节点
  • floor用于存放tmp中的节点,swap用于存放tmp中子节点
  • 通过遍历tmp中的节点,将节点的根节点(t.val)放入floor中,将节点的左右节点(t.left, t.right)放入swap中
  • 最后将floor放入res中, 再将swap赋给tmp

Demo

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
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution():
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        # 如果根节点为空,直接返回空列表
        if not root:
            return []
        # res列表用于存放返回的结果
        res = []
        # tmp列表用于存放树的每一层节点(首先把根节点放进去)
        tmp = [root]
        # 如果根节点不为空就执行下面的逻辑
        while tmp:
            # 定义列表floor用于存放tmp的值
            floor = []
            # 定义列表用于存放tmp的子节点的值
            swap = []
            # 下面for循环的逻辑是将tmp中的节点值加入floor, 将tmp中的左右节点加入swap
            for t in tmp:
                floor.append(t.val)
                if t.left:
                    swap.append(t.left)
                if t.right:
                    swap.append(t.right)
            # 遍历完后,将swap列表中的值赋给tmp,所以tmp就有了所有的子节点了
            res.append(floor)
            tmp = swap
        return res