二叉树
分类
满二叉树
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
深度为k，则有2(k−1)个节点的二叉树
完全二叉树
完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大
二叉搜索树
二叉搜索树是一个有序树
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
遍历方式🐣
- 深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历
二叉树的定义
1
2
3
4
5
6
| struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
|
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;
}
}
|
1
2
3
4
5
| class TreeNode:
def __init__(self, val, left = None, right = None):
self.val = val
self.left = left
self.right = right
|
递归遍历
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
51
|
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);
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
void inorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}
void postorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
postorder(root.left, list);
postorder(root.right, list);
list.add(root.val);
}
}
|
迭代遍历
迭代遍历的常见问题是：无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况
那么解决思路是将访问节点放入栈中，把要处理节点也放入栈中但是要做标记。
标记：要处理的节点放入栈中后，紧接着放入一个空指针作为标记。当遇到空指针时，将处理节点放入栈中
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
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);
} else {
st.pop();
node = st.peek();
st.pop();
result.add(node.val);
}
}
return result;
}
}
class Solution {
public List<Integer> inorderTraversal(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);
st.push(node);
st.push(null);
if (node.left!=null) st.push(node.left);
} else {
st.pop();
node = st.peek();
st.pop();
result.add(node.val);
}
}
return result;
}
}
class Solution {
public List<Integer> postorderTraversal(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();
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;
}
}
|
层序遍历
利用队列先进先出的特性进行层序遍历
若要求自底向上的层序遍历即将下面的输出结果数组反转一下即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
if (root != null) queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> temp = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
temp.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
ans.add(temp);
}
return ans;
}
}
|
算法题
二叉树的最大深度
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 maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
int depth = 0;
while (!que.isEmpty())
{
int len = que.size();
while (len > 0)
{
TreeNode node = que.poll();
if (node.left != null) que.offer(node.left);
if (node.right != null) que.offer(node.right);
len--;
}
depth++;
}
return depth;
}
}
|
二叉树的最小深度
- 利用层序遍历，统计深度，当遇到第一个左右子节点都为空时，返回深度
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 minDepth(TreeNode root){
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()){
int size = queue.size();
depth++;
TreeNode cur = null;
for (int i = 0; i < size; i++) {
cur = queue.poll();
if (cur.left == null && cur.right == null){
return depth;
}
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
}
return depth;
}
}
|
