刷穿剑指offer-Day22-树I 树的基础知识讲解！
树的概念与名词解释
树（Tree）是一种抽象的数据结构，之所以把“它”叫做树，是因为它看起来像是一棵倒挂着的树，即根在上，叶朝下。
一棵树是由n（n>=0）个元素组成的，当n = 0时，树称为空(null或empty)树。每个元素称为一个节点(node)，而最顶端的节点成为根节点。
树中的名词和概念很多，在这里需要有个大概的了解：
| 名词 | 解释 |
|---|---|
| 父节点 | 若一个节点含有子节点，则这个节点称为其子节点的父节点 |
| 子节点 | 一个节点含有的子树的根节点称为该节点的子节点 |
| 兄弟节点 | 具有相同父节点的节点互称为兄弟节点 |
| 节点的层次 | 从根开始定义起，根为第1层，根的子节点为第2层，以此类推 |
| 深度 | 对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0 |
| 高度 | 对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0 |
| 堂兄弟节点 | 父节点在同一层的节点互为堂兄弟 |
| 节点的度 | 一个节点含有的子树的个数称为该节点的度 |
| 树的度 | 一棵树中，最大的节点度称为树的度 |
二叉树
看到上面树的度，引出了我们算法中常见的一类树结构 二叉树。所谓二叉树，就是每个节点最多含有两个子树（左子树和右子树）的树称为二叉树。
而针对二叉树的结构与数据存储又分为了以下几种类型：
| 分类 | 特点 |
|---|---|
| 完全二叉树 | 对于一棵二叉树，假设其深度为d（d>1），除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列 |
| 满二叉树 | 二叉树中所有非叶子结点的度都是2，且叶子结点都在同一层次上 |
| 平衡二叉树 | 当且仅当任何节点的两棵子树的高度差不大于1的二叉树 |
| 二叉搜索树 | 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； |
二叉树的定义
一般而言，二叉树的算法题目都是以链式存储的非线性结构。力扣上涉及二叉树的题目，都会默认定义好树的结构，定义方式如下：
Python：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
Java:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
二叉树的三种基础遍历
二叉树的题目，绝大多数都是在考树的搜索。其中入门的是二叉树的前、中、后序遍历：
- 前序遍历：遍历顺序规则为【根左右】
- 中序遍历：遍历顺序规则为【左根右】
- 后序遍历：遍历顺序规则为【左右根】
举个例子：
- 逐层遍历：EAGCFBD
- 前序遍历：EACBDGF
- 中序遍历：ABCDEGF
- 后序遍历：BDCAFGE
逐层遍历，其实就是上节课讲解队列的基础操作时，涉及到的二叉树的广度优先搜索。剩下的三种遍历方式，大家可以对照下是否和你想的结果一样。
那么，我们该通过什么方式来实现二叉树的遍历操作呢？有递归 、 迭代两种方式。
递归比较好理解，迭代又是什么？其实，递归的操作，是隐式的通过栈内存完成递归。而迭代则需要我们自己模拟栈内存。让我们拿一道题目来练练手吧。
144.二叉树的前序遍历
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
难度：简单
题目
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
提示：
- 树中节点数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
示例
示例 1：
1
\
2
/
3
输入：root = [1,null,2,3]
输出：[1,2,3]
分析
先来说说递归，使用递归的方式来完成前中后遍历，只需要修改递归函数的节点顺序即可完成。
牢记如下访问顺序即可。
- 前序遍历：遍历顺序规则为【根左右】
- 中序遍历：遍历顺序规则为【左根右】
- 后序遍历：遍历顺序规则为【左右根】
至于迭代，这需要我们将递归过程中隐式的内存栈，通过自己定义的方式来实现。
这里则要求我们，在掌握之前学习的链表和栈的操作基础上，才更好理解这道题目。
- 首先，我们需要创建一个栈，然后创建cur节点指向root
- 然后当栈或者cur节点不为空时，启动while循环操作
- 由于第一个入栈的是root节点，则我们直接保存它的值
- 然后循环获取当前指针的左子树指针（即cur.left），保存值并加入栈中，直到指向叶子结点终止
- 之后弹出当前栈，将指针指向cur.right继续上述操作。
- 直到最终遍历完成，返回节点的所有值。
让我们来看看代码的具体实现
递归解题
Python：
class Solution:
def preorderTraversal(self, root):
ret = []
def dfs(tree):
if not tree:
return
if tree:
ret.append(tree.val)
dfs(tree.left)
dfs(tree.right)
dfs(root)
return ret
Java：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
dfs(root, ret);
return ret;
}
private void dfs(TreeNode tree, List<Integer> ret){
if (tree == null){
return;
}
ret.add(tree.val);
dfs(tree.left, ret);
dfs(tree.right, ret);
}
}
迭代解题
Python：
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
ret = list()
if not root:
return ret
stack = []
cur = root
while stack or cur:
while cur:
ret.append(cur.val)
stack.append(cur)
cur = cur.left
cur = stack.pop()
cur = cur.right
return ret
Java：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<Integer>();
if (root == null) {
return ret;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
ret.add(cur.val);
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
cur = cur.right;
}
return ret;
}
}
通过这道题，让大家对二叉树的遍历有所了解，下来大家可以完成这两道题目，用以加深了解。
今天的树专题概念篇就到这里，明天就要正式开始刷题之旅了，基础很重要一定要吃透了在往后走哦，明天见！
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
