二叉树注意点
确定那种遍历方法（BFS，DFS）如果是深度优先遍历，确定是前序后序还是中序。确定遍历方法的哪种实现（递归，迭代）
二叉树的种类
在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。
满二叉树
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。
完全二叉树
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
所有满二叉树都是完全二叉树，但并非所有完全二叉树都是满二叉树。
二叉搜索树
前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树
平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉树的存储方式
二叉树可以链式存储，也可以顺序存储。
链式存储方式就用指针， 顺序存储的方式就是用数组。
链式存储如图：
数组实现如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
二叉树的遍历方式
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 广度优先遍历：一层一层的去遍历。
那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：
- 深度优先遍历
- 前序遍历（递归法，迭代法）——中左右
- 中序遍历（递归法，迭代法）——左中右
- 后序遍历（递归法，迭代法）——左右中
- 广度优先遍历
二叉树的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
|
java底层对象的实现方式：
ArrayList： 基于动态数组实现。内部使用数组来存储元素，当数组容量不足时，会自动进行扩容。
LinkedList： 基于双向链表实现。每个节点包含数据和指向前后节点的引用，支持快速的插入和删除操作。
HashSet： 基于哈希表实现。元素存储在哈希表的桶中，通过哈希码确定元素在桶中的位置。
TreeSet： 基于红黑树实现。红黑树是一种自平衡的二叉查找树，用于保持元素的有序性。
HashMap： 基于哈希表实现。使用键的哈希码来确定键值对在哈希表中的位置。
TreeMap： 基于红黑树实现。与TreeSet类似，使用红黑树来保持键的有序性。
深度优先遍历（DFS）-递归遍历
前边我们已经知道了前序遍历中序遍历已经后序遍历的顺序每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！
确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，因为递归是动态变化的，所以参数值应是随着递归会变化的参数值。并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
1
| public void preorder(TreeNode root, List<Integer> result)
|
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
1
2
3
| if (root == null) {
return;
}
|
确定单层递归的逻辑： 确定每一层递归需要处理的信息。单层需要做哪些处理，递归的位置在哪。
1
2
3
| result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
|
完整的递归遍历二叉树的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
|
深度优先遍历（DFS）-迭代遍历
可以看到递归遍历二叉树很简单，但是迭代遍历可能有些不同，并且这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！所以前序遍历代码还不同于中序遍历
前序遍历
设置一个栈每次弹出他们的父亲节点然后添加左右孩子节点。这样看起来也是实现递归，因为同理递归的实现也是依靠栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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;
}
}
|
中序遍历
中序遍历不同于前序主要原因是遍历节点不是处理的节点，需要创建一个cur的指针，中序遍历是左中右，所以一路向左到叶子节点。最左的叶子节点先弹出，并加入结果，然后遍历叶子的右同样为null的话证明他的节点遍历完了，此时cur==叶子节点的负节点把他加入结果遍历右节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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;
}
}
|
后续遍历
翻转前序遍历即可
1
| Collections.reverse(result);
|
统一迭代
如何让迭代风代统一呢那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
st.pop();
if (node.right!=null) st.push(node.right);
if (node.left!=null) st.push(node.left);
st.push(node);
st.push(null);
st.pop();
if (node.right!=null) st.push(node.right);
st.push(node);
st.push(null);
if (node.left!=null) st.push(node.left);
st.pop();
st.push(node);
st.push(null);
if (node.right!=null) st.push(node.right);
if (node.left!=null) st.push(node.left);
} else {
st.pop();
node = st.peek();
st.pop();
result.add(node.val);
}
}
return result;
}
}
|
广度优先搜索（BFS）
层序遍历递归用数组实现，传递参数时传递深度，由此可以找到，迭代是每次循环都添加新的一层到队列，秉承先进先出可以保证顺序一致。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public List<List<Integer>> resList = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
checkFun02(root);
return resList;
}
public void checkFun01(TreeNode node, Integer deep) {
if (node == null) return;
deep++;
if (resList.size() < deep) {
List<Integer> item = new ArrayList<Integer>();
resList.add(item);
}
resList.get(deep - 1).add(node.val);
checkFun01(node.left, deep);
checkFun01(node.right, deep);
}
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);
}
}
}
|
226.翻转二叉树
力扣题目链接
把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果，所以这个就属于一个遍历的应用主要看在遍历过程中交换的位置在哪里。
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
invertTree(root.left);
invertTree(root.right);
swapChildren(root);
return root;
}
private void swapChildren(TreeNode root) {
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
}
|
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {return null;}
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
deque.offer(root);
while (!deque.isEmpty()) {
int size = deque.size();
while (size-- > 0) {
TreeNode node = deque.poll();
swap(node);
if (node.left != null) deque.offer(node.left);
if (node.right != null) deque.offer(node.right);
}
}
return root;
}
public void swap(TreeNode root) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
|
101. 对称二叉树
力扣题目链接
要比较的并不是左右节点而是两个子树的里侧和外侧的元素是否相等
确定终止条件
要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
- 左节点为空，右节点不为空，不对称，return false
- 左不为空，右为空，不对称 return false
- 左右都为空，对称，返回true
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
- 左右都不为空，比较节点数值，不相同就return false
迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public boolean isSymmetric3(TreeNode root) {
Queue<TreeNode> deque = new LinkedList<>();
deque.offer(root.left);
deque.offer(root.right);
while (!deque.isEmpty()) {
TreeNode leftNode = deque.poll();
TreeNode rightNode = deque.poll();
if (leftNode == null && rightNode == null) {
continue;
}
if (leftNode == null && rightNode != null) {
return false;
}
if (leftNode != null && rightNode == null) {
return false;
}
if (leftNode.val != rightNode.val) {
return false;
}
deque.offer(leftNode.left);
deque.offer(rightNode.right);
deque.offer(leftNode.right);
deque.offer(rightNode.left);
}
return true;
}
|
104.二叉树的最大深度
力扣题目链接
就是看看二叉树有多少层
本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）就是根向下数
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）就是从叶子向上数。
递归法
递归法就是再求从叶子节点开始以贪心的方式找最大深度
1
2
3
4
5
6
7
8
9
10
11
12
13
| class solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
|
迭代法
迭代法是层序遍历的模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class solution {
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
int depth = 0;
while (!deque.isEmpty()) {
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode node = deque.poll();
if (node.left != null) {
deque.offer(node.left);
}
if (node.right != null) {
deque.offer(node.right);
}
}
}
return depth;
}
}
|
111.二叉树的最小深度
力扣题目链接
不能直接的使用最大深度取一个最小值的情况，因为还有没有节点的情况，最小深度是指从根到叶子，并不是如果没有节点就是最小比如下图。叶子节点的特征是左右子树都为空。所以第一次判断右子树为空左子树不为空应该返回的是左子树+1的深度。
递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left == null) {
return rightDepth + 1;
}
if (root.right == null) {
return leftDepth + 1;
}
return Math.min(leftDepth, rightDepth) + 1;
}
}
|
迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
int depth = 0;
while (!deque.isEmpty()) {
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode poll = deque.poll();
if (poll.left == null && poll.right == null) {
return depth;
}
if (poll.left != null) {
deque.offer(poll.left);
}
if (poll.right != null) {
deque.offer(poll.right);
}
}
}
return depth;
}
}
|
222.完全二叉树的节点个数
力扣题目链接
通用解决方法
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
int leftNum = getNodesNum(root.left);
int rightNum = getNodesNum(root.right);
int treeNum = leftNum + rightNum + 1;
return treeNum;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int result = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size -- > 0) {
TreeNode cur = queue.poll();
result++;
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
}
return result;
}
}
|
完全二叉树解决方法
但是完全二叉树是否有更简单的求法呢，当然，就是判断他的左右子树的深度是否完全一样如果完全一样就是一个满二叉树就可以用满二叉树的计算公式 2^树深度 - 1 因为完全二叉树要求如果有节点不满那么一定在左边，所以如果深度不一样则说明不是满二叉树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0, rightDepth = 0;
while (left != null) {
left = left.left;
leftDepth++;
}
while (right != null) {
right = right.right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
|