1. 理论基础

1.1种类

解题碰到的二叉树主要两种:满二叉树和完全二叉树.

1. 满二叉树

定义:一颗二叉树只有度为0和2的节点,并且度为0的结点在同一层上,就是满二叉树

满二叉树

2. 完全二叉树

• 如果有没填满的节点,只能是最底层,其他层每层节点数都达到最大值.
• 最后一层节点必须全在最左边

完全二叉树

前面的这两个分类是没有数值的,接下来介绍一个有数值的:

3. 二叉搜索树

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  它的左、右子树也分别为二叉排序树

image.png

4. 平衡二叉搜索树(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){
}

2. 确定终止条件
   当前节点是null就说明没节点了

if(root === null) return;

3.确定单层递归逻辑,
前序遍历就是中左右.

在遍历外定义好的存储结果的数组let res = []

const bfs = function(root){
  ...
  res.push(root);
  bfs.(root.left)
  bfs.(root.right)
}

3.迭代遍历

4.统一迭代