1. 理论基础
1.1种类
解题碰到的二叉树主要两种:满二叉树和完全二叉树.
- 满二叉树
定义:一颗二叉树只有度为0和2的节点,并且度为0的结点在同一层上,就是满二叉树
满二叉树
- 完全二叉树
- 如果有没填满的节点,只能是最底层,其他层每层节点数都达到最大值.
- 最后一层节点必须全在最左边
完全二叉树
前面的这两个分类是没有数值的,接下来介绍一个有数值的:
- 二叉搜索树
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
image.png
- 平衡二叉搜索树(AVL树)
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
顺序存储
1.2存储方式
二叉树可以链式存储(用指针),可以顺序存储(用数组)
链式存储
image.png
1.3遍历方式
首先是两大类:
- DFS深度优先遍历(往深处走,遇到叶节点再往回)
- BFS广度优先遍历(一层一层走)
然后从这个基础上扩展:
image.png
判断深度优先的三个数序的方法:这里前中后，其实指的就是中间节点的遍历顺序
image.png
1.4 二叉树定义JS版本
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
2.递归遍历
按照三要素来写:
image.png
比如js的前序遍历:
1.确定递归函数的参数和返回值
在每次递归的时候都是把当前节点push到存的数组里,所以没有return 值.参数就是当前的节点
const dfs = function(root){
}
- 确定终止条件
当前节点是null就说明没节点了
if(root === null) return;
3.确定单层递归逻辑,
前序遍历就是中左右.
在遍历外定义好的存储结果的数组let res = []
const bfs = function(root){
...
res.push(root);
bfs.(root.left)
bfs.(root.right)
}
