二叉树
二叉树遍历
- 前序遍历：先访问根节点，再前序遍历左子树，再前序遍历有子树
- 中序遍历：先中序遍历左子树，在访问根节点，再中序遍历右子树
- 后序遍历：先后序遍历左子树，再后续遍历由子树，再访问根节点
二叉树结构定义
1
2
3
4
5
6
7
8
9
10
11
12
| 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
6
7
8
| public void preorderTraversal(TreeNode root, List<Integer> valList){
if(root == null){
return;
}
valList.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
|
前序非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public void preorderTraversal(TreeNode root, List<Integer> valList){
if(root == null){
return;
}
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
while(!stack.isEmpty() || root!=null) {
while(root!=null) {
stack.push(root);
valList.add(root.val);
root = root.left;
}
root = stack.pop();
root = root.right;
}
}
|
中序递归
1
2
3
4
5
6
7
8
| public void inorderTraversal(TreeNode root, List<Integer> valList){
if(root == null){
return;
}
inorderTraversal(root.left);
valList.add(root.val);
inorderTraversal(root.right);
}
|
中序非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public void inorderTraversal(TreeNode root, List<Integer> valList){
if(root == null){
return;
}
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
while(!stack.isEmpty() || root!=null) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
valList.add(root.val);
root = root.right;
}
}
|
后序递归
1
2
3
4
5
6
7
8
| public void postorderTraversal(TreeNode root, List<Integer> valList){
if(root == null){
return;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
valList.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
| public void postorderTraversal(TreeNode root, List<Integer> valList){
if(root == null){
return;
}
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode lastNode = root;
while(!stack.isEmpty() || root!=null) {
while(root!=null) {
stack.push(root);
root = root.left;
}
root = stack.peek();
if(root.right == null || root.right == lastNode){
valList.add(root.val);
lastNode = root;
stack.pop();
root = null;
}else{
root = root.right;
}
}
}
|
DFS 深度搜索-从上到下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public List<Integer> preorderTraversal(TreeNode root){
List<Integer> valList = new ArrayList<>();
dfs(root,valList);
return valList;
}
public void dfs(TreeNode root, List<Integer> valList){
if(root == null){
return;
}
valList.add(root.val);
dfs(root.left);
dfs(root.right);
}
|
DFS 深度搜索-从下向上（分治法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public List<Integer> preorderTraversal(TreeNode root){
return divideAndConquer(root);
}
public List<Integer> divideAndConquer(TreeNode root){
List<Integer> valList = new ArrayList<>();
if(root == null){
return valList;
}
valList.add(root.val);
valList.addAll(divideAndConquer(root.left));
valList.addAll(divideAndConquer(root.right));
return valList;
}
|
DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并
BFS层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public List<Integer> bfs(TreeNode root){
List<Integer> valList = new ArrayList<>();
if(root == null){
return valList;
}
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode tree = queue.remove();
if(tree != null){
if (tree.left != null){
queue.add(tree.left);
}
if (tree.right != null){
queue.add(tree.right);
}
list.add(tree.val);
}
}
return valList;
}
|
分治法应用
先分别处理局部，再合并结果
适用场景
分治法模板
1
2
3
4
5
6
7
8
9
10
11
12
13
| public List<Integer> traversal(TreeNode root){
List<Integer> valList = new ArrayList<>();
if(root == null){
return valList;
}
valList.add(root.val);
valList.addAll(traversal(root.left));
valList.addAll(traversal(root.right));
return valList;
}
|
归并排序
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
| public int[] sort(int[] nums) {
return mergeSort(nums);
}
public int[] mergeSort(int[] nums) {
if (nums.length <= 1) {
return nums;
}
int mid = nums.length / 2;
int[] left = new int[mid];
int[] right = new int[nums.length - mid];
for (int i = 0; i < nums.length; i++) {
if (i < mid) {
left[i] = nums[i];
} else {
right[i - mid] = nums[i];
}
}
return merge(mergeSort(left), mergeSort(right));
}
public int[] merge(int[] left, int[] right) {
int leftIndex = 0;
int rightIndex = 0;
int[] result = new int[left.length + right.length];
for (int i = 0; i < result.length; i++) {
if (leftIndex == left.length && rightIndex < right.length) {
result[i] = right[rightIndex];
rightIndex++;
} else if (leftIndex < left.length && rightIndex == right.length) {
result[i] = left[leftIndex];
leftIndex++;
} else {
if (left[leftIndex] < right[rightIndex]) {
result[i] = left[leftIndex];
leftIndex++;
} else {
result[i] = right[rightIndex];
rightIndex++;
}
}
}
return 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
| public int[] sort(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int start, int end) {
if (start < end) {
int mid = partition(nums, start, end);
quickSort(nums, 0, mid - 1);
quickSort(nums, mid + 1, end);
}
}
public int partition(int[] nums, int start, int end) {
int temp = nums[end];
for (int i = start; i < end; i++) {
if (nums[i] < temp) {
swap(nums, start, i);
start++;
}
}
swap(nums, start, end);
return start;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
|
题目
leetcode110-二叉树的中序遍历
leetcode104-二叉树的最大深度
leetcode110-平衡二叉树
leetcode124-二叉树中的最大路径和
leetcode144-二叉树的前序遍历
leetcode144-二叉树的后序遍历