树相关概念:
- 节点的度:一个节点含有的子树的个数称为该节点的度;
- 树的度:一棵树中,最大的节点度称为树的度;
- 叶节点或终端节点:度为零的节点;
- 非终端节点或分支节点:度不为零的节点;
- 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
- 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
- 兄弟节点:具有相同父节点的节点互称为兄弟节点;
- 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
- 深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0;
- 高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;
- 堂兄弟节点:父节点在同一层的节点互为堂兄弟;
- 节点的祖先:从根到该节点所经分支上的所有节点;
- 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林:由m(m>=0)棵互不相交的树的集合称为森林;
父亲节点与子节点关系
二叉树的遍历方式
非递归方式
风格不统一遍历法
// 前序遍历顺序:中-左-右,入栈顺序:中-右-左
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
return result;
}
}
// 中序遍历顺序: 左-中-右 入栈顺序: 左-右
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()){
if (cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
}
// 后序遍历顺序 左-右-中 入栈顺序:中-左-右 出栈顺序:中-右-左, 最后翻转结果
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null){
stack.push(node.left);
}
if (node.right != null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
}
风格统一
中序遍历
中序遍历的顺序是左子树 –> 根节点 –> 右子树,在访问左子树和右子树时也以同样的方式访问节点。 先找到左子树的最左节点,再加入中点,再到右节点(作为根节点继续遍历)
class Solution {
// 中序遍历找到第k小个数
public int kthSmallest(TreeNode root, int k) {
// 栈迭代中序遍历
Deque<TreeNode> st = new ArrayDeque<>();
while (root !=null || !st.isEmpty()){
// 先遍历左子树
while (root !=null){
st.push(root);
root = root.left;
}
// 拿到根节点,此时开始按大小顺序遍历得到数
root = st.pop();
k--;
// 此时是否遍历到了最小k数
if (k == 0){
break;
}
// 记录右子树根节点
root = root.right;
// st.push(root);
}
return root.val;
}
}
层次遍历
// 102.二叉树的层序遍历
class Solution {
public List<List<Integer>> resList = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
//checkFun01(root,0);
checkFun02(root);
return resList;
}
//DFS--递归方式
public void checkFun01(TreeNode node, Integer deep) {
if (node == null) return;
deep++;
// 收集结果
if (resList.size() < deep) {
//当层级增加时,list的Item也增加,利用list的索引值进行层级界定
List<Integer> item = new ArrayList<Integer>();
resList.add(item);
}
resList.get(deep - 1).add(node.val);
checkFun01(node.left, deep);
checkFun01(node.right, deep);
}
//BFS--迭代方式--借助队列
public void checkFun02(TreeNode node) {
if (node == null) return;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
// 层序遍历
while (!que.isEmpty()) {
List<Integer> itemList = new ArrayList<Integer>();
int len = que.size();
while (len > 0) {
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if (tmpNode.left != null) que.offer(tmpNode.left);
if (tmpNode.right != null) que.offer(tmpNode.right);
len--;
}
resList.add(itemList);
}
}
}
自上向下
自下而上
通用算法
深度优先
广度优先
广搜和深搜都只是两种不同的搜索方式,给做题的时候提供遍历的思路,对于遍历过的内容,以及要解决的问题,可以由这种搜索方式提供解决思路。 而迭代法和递归法则是实现这两种(深搜广搜)算法的实现方式,既可以由迭代+栈进行深搜,也可以通过递归实现深搜;可以用迭代+队列实现广搜(层次遍历入队列形式)
二叉树分类
二叉搜索树
定义
二叉排序树(Binary Sort Tree, BST),也称二叉查找树。 二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二叉树:
- 1) 若左子树非空,则左子树上所有结点关键字均小于根结点的关键字值;
- 2) 若右子树非空,则右子树上所有结点关键字均大于根结点的关键字值;
- 3) 左、右子树本身也分别是一棵二叉排序树。
由定义可知,二叉排序树是一个递归的数据结构,可以方便的使用递归算法对二叉排序树进行各种运算。根据二叉树的定义,可得左子树结点值 < 根结点值 < 右子树结点值。 所以,对二叉排序树进行中序遍历,可以得到一个递增的有序序列。
如何构建
由于二叉搜索树的中序遍历是升序的,所以可以在序列中选出一个数作为根节点,该数左边的数用来构建左子树,右边的数用来构建右子树。这样可以得到一颗二叉搜索树。 具体可以用递归的方式来分别构建左右子树 递归构建伪代码:
// 输入:一个有序数组,代表平衡二叉树搜索树节点的值
public TreeNode dfs(子树构建范围:int[] nums, int l, int r){
// 终止条件:子树为空
if (l>r){
return null;
}
// 寻找根节点-> 在数组中的位置
int mid = num[l+(r-l)/2];
// 构造根节点
TreeNode root = new TreeNode(mid);
root.left = dfs(左子树范围);
root.rigth = dfs(右子树范围);
// 返回最后选中的节点
return root;
}
平衡二叉树
定义
平衡二叉树是左子树与右子树的最高深度不超过1的二叉树