最小高度树
题目说明：
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
解法一：递归
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
|
在这道题中，left和right并不代表左右结点的值，而是相应节点在数组nums中的位置，这个在编写递归开始前的判断是很重要的。
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length==0){
return null;
}
return CreateMinitree(nums,0,nums.length-1);
}
public TreeNode CreateMinitree(int nums[],int left,int right){
if(left>=right||right>nums.length||left<0){
return null;
}
int mid = (left+right)/2;
TreeNode n = new TreeNode(nums[mid]);
n.left = CreateMinitree(nums,left,mid-1);
n.right = CreateMinitree(nums,mid+1,right);
return n;
}
}
|
二叉树的深度
题目说明：
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
解法一：递归
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;
}else{
int maxLeftHeight = maxDepth(root.left);
int maxRightHeight = maxDepth(root.right);
return Math.max(maxLeftHeight,maxRightHeight)+1;
}
}
}
|
剑指offer27.二叉树的镜像/翻转二叉树
题目说明：
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
![]()
![]()
解法一：DFS递归
- 根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。
递归解析：
- **终止条件 **:当节点 root 为空时（即越过叶节点），则返回 null ；
- 递推工作：
- 初始化节点 tmp ，用于暂存 root 的左子节点；
- 开启递归右子节点mirrorTree(root,right)，并将返回值作为root的左子节点。
- 开启递归右子节点mirrorTree(root,left)，并将返回值作为root的右子节点。
- 返回值: 返回新构建的树的root结点。
Q：为何需要暂存root的左子节点？
A：在递归完成root的右子节点后，此时root.left的值已经发生改变，此时再进行递归左子树就会出现问题。
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
|
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root==null){
return null;
}
TreeNode temp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(temp);
return root;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
|
解法二：辅助栈
- 利用栈（或队列）遍历树的所有节点 nodenod**e ，并交换每个 node的左 / 右子节点。
合并两棵二叉树
题目概述：
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
|
解法一：DFS深度优先搜索
可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。
两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。
如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。
对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。这是一个递归的过程。
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
|
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null){
return root2;
}
if(root2==null){
return root1;
}
TreeNode merged = new TreeNode(root1.val+root2.val);
merged.left = mergeTrees(root1.left,root2.left);
merged.right = mergeTrees(root2.right ,root1.right );
return merged;
}
}
|
复杂度分析：
![]()
解法二：广度优先搜索BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 也可以使用广度优先搜索合并两个二叉树。首先判断两个二叉树是否为空，如果两个二叉树都为空，则合并后的二叉树也为空，如果只有一个二叉树为空，则合并后的二叉树为另一个非空的二叉树。
如果两个二叉树都不为空，则首先计算合并后的根节点的值，然后从合并后的二叉树与两个原始二叉树的根节点开始广度优先搜索，从根节点开始同时遍历每个二叉树，并将对应的节点进行合并。
使用三个队列分别存储合并后的二叉树的节点以及两个原始二叉树的节点。初始时将每个二叉树的根节点分别加入相应的队列。每次从每个队列中取出一个节点，判断两个原始二叉树的节点的左右子节点是否为空。如果两个原始二叉树的当前节点中至少有一个节点的左子节点不为空，则合并后的二叉树的对应节点的左子节点也不为空。对于右子节点同理。
如果合并后的二叉树的左子节点不为空，则需要根据两个原始二叉树的左子节点计算合并后的二叉树的左子节点以及整个左子树。考虑以下两种情况：
如果两个原始二叉树的左子节点都不为空，则合并后的二叉树的左子节点的值为两个原始二叉树的左子节点的值之和，在创建合并后的二叉树的左子节点之后，将每个二叉树中的左子节点都加入相应的队列；
如果两个原始二叉树的左子节点有一个为空，即有一个原始二叉树的左子树为空，则合并后的二叉树的左子树即为另一个原始二叉树的左子树，此时也不需要对非空左子树继续遍历，因此不需要将左子节点加入队列。
对于右子节点和右子树，处理方法与左子节点和左子树相同。
|
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
|
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null){
return root2;
}
if(root2==null){
return root1;
}
TreeNode merged = new TreeNode(root1.val+root2.val);
Queue<TreeNode> queue1 = new LinkedList<>();
Queue<TreeNode> queue2 = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(merged);
queue1.offer(root1);
queue2.offer(root2);
while(!queue1.isEmpty()&&!queue2.isEmpty()){
TreeNode node1 = queue1.poll();
TreeNode node = queue.poll();
TreeNode node2 = queue2.poll();
TreeNode left1 = node1.left,left2 = node2.left,right1 = node1.right,right2 = node2.right;
if(left1!=null || left2!=null){
if(left1!=null&&left2!=null){
TreeNode left = new TreeNode(left1.val+left2.val);
node.left = left;
queue.offer(left);
queue1.offer(left1);
queue2.offer(left2);
}else if(left1!=null){
node.left = left1;
}else if(left2!=null){
node.left = left2;
}
}
if(right1!=null || right2!=null){
if(right1!=null&&right2!=null){
TreeNode right = new TreeNode(right1.val+right2.val);
node.right = right;
queue.offer(right);
queue1.offer(right1);
queue2.offer(right2);
}else if(right1!=null){
node.right = right1;
}else if(right2!=null){
node.right = right2;
}
}
}
return merged;
}
}
|
复杂度分析：
![]()
二叉搜索树的范围和
二叉树的最大深度
二叉树的层平均值
题目描述：
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1：
1
2
3
4
5
6
7
8
9
| 输入：
3
/ \
9 20
/ \
15 7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
|
提示：
解法一: 深度优先搜索
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
|
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Integer> counts = new ArrayList<Integer>();
List<Double> sums = new ArrayList<Double>();
dfs(root,0,counts,sums);
List<Double> averages = new ArrayList<Double>();
int size = sums.size();
for(int i=0;i<size; i++){
averages.add(sums.get(i)/counts.get(i));
}
return averages;
}
public void dfs(TreeNode root,int level,List<Integer> counts,List<Double> sums){
if(root==null){
return ;
}
if(level<sums.size()){
sums.set(level,sums.get(level)+root.val);
counts.set(level,counts.get(level)+1);
}else{
sums.add(1.0*root.val);
counts.add(1);
}
dfs(root.left,level+1,counts,sums);
dfs(root.right,level+1,counts,sums);
}
}
|
复杂度分析：
![image-20210325152848238]()
解法二：广度优先搜索
复杂度分析：
剑指offer68 二叉树的最近公共祖先
题目描述
解法一：
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
|
class Solution {
private TreeNode ans;
public Solution(){
this.ans = null;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
thist.dfs(root,p,q);
return this.ans;
}
public boolean dfs(TreeNode root,TreeNode p,TreeNode q){
if(root==null){
return false;
}
boolean flson = dfs(root.left,p,q);
boolean frson = dfs(root.right,p,q);
if((flson&&frson) || ((root.val==p.val||root.val==q.val)&&(flson||frson))){
ans = root;
}
return flson || frson || (root.val==p.val || root.val ==q.val);
}
}
|
复杂度分析：
![image-20210326170817422]()
解法二：存储父节点
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
|
class Solution {
Map<Integer,TreeNode> map = new HashMap<>();
Set<Integer> set = new HashSet<>();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root);
while(p!=null){
set.add(p.val);
p = map.get(p.val);
}
while(q!=null){
if(set.contains(q.val)){
return q;
}
q = map.get(q.val);
}
return null;
}
public void dfs(TreeNode root){
if(root.left !=null){
map.put(root.left.val,root);
dfs(root.left);
}
if(root.right !=null){
map.put(root.right.val,root);
dfs(root.right);
}
}
}
|
复杂度分析
![image-20210326174012955]()
