• 二叉树的第 i 层最多有$2^{i-1}$个节点

  • 深度为 h 的二叉树最多有$2^h - 1$个节点。定义根节点深度为1。

  • $n_0$(度为 0 的节点,叶子节点),$n_1$(度为 1 的节点),$n_2$(度为 2 的节点),有 $n_0 = n_2 + 1$

1
2
3
n0+n1+n2-1 = 0*n0+1*n1+2*n2

n0 = n2+1

分类

完全二叉树和满二叉树

完全二叉树 满二叉树
节点数 $2^{h-1} \le k \le 2^h - 1$ $2^h -1$
树高 $h = lgk +1$ $h = lg(k + 1)$
描述 除了最后一层其余都是满的。 满足最多的节点数。

应用

二叉树可以实现二叉树和二叉搜索树,用于排序和搜索。

  • 二叉堆(Binary Heap):一棵完全二叉树,并且父节点的值都大于等于子节点的值。
  • 二叉搜索树(BST):symmetric order的二叉树,即左子树的全部值 < 父节点 < 右子树的全部值

二叉树的遍历

二叉树的遍历用递归实现代码十分简介,因为树结构就是递归定义的。

前序遍历

根节点 -> 左孩子 -> 右孩子

1
2
3
4
5
6
7
8
private void preOrder(TreeNode root) {
if (root == null) {
return;
}
preOrderList.add(root);
preOrder(root.left);
preOrder(root.right);
}

中序遍历

左孩子 -> 根节点 -> 右孩子

1
2
3
4
5
6
7
8
private void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
inOrderList.add(root);
inOrder(root.right);
}

后序遍历

左孩子 -> 右孩子 -> 根节点

1
2
3
4
5
6
7
8
private void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
postOrderList.add(root);
}

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
private Queue<TreeNode> levelOrderQueue = new LinkedList<>();
private ArrayList<TreeNode> levelOrderList = new ArrayList<>();
// Just likes BFS, and preOrder, inOrder and postOrder are like DFS
private void levelOrder(TreeNode root) {
levelOrderQueue.add(root);
while (!levelOrderQueue.isEmpty()) {
TreeNode node = levelOrderQueue.poll();
levelOrderList.add(node);
if (node.left != null) levelOrderQueue.add(node.left);
if (node.right != null) levelOrderQueue.add(node.right);
}
}

相关面试题

验证二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

  • 思路:二叉树的后序遍历后,根节点肯定在数组最后。根据 BST 的性质左子树 < 父节点 < 右子树。首先找到左子树的位置,把序列分成两段,前一段都小于根,后一段都大于根。 这两棵子树也符合这样的定义。也就是递归定义,可以用递归解决。

  • 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
private boolean valid(int[] squence, int start, int end) {
if (start >= end) return true;
int p = end;
// find the left tree & valid right
while (p > start && squence[end] < squence[p - 1]) p--;
// valid left
for (int i = p - 1; i >= start; i--) {
if (squence[i] > squence[end]) return false;
}
return valid(squence, start, p - 1) && valid(squence, p, end - 1);
}

public boolean VerifySquenceOfBST(int[] sequence) {
if (sequence.length == 0) return false;
return valid(sequence, 0, sequence.length - 1);
}
}

参考