二叉树题集
Leetcode105
这道题要求我们根据二叉树的前序遍历和中序遍历还原这棵二叉树。这是一个定理：只要给定一棵树的前序遍历和中序遍历或者后序遍历和中序遍历，我们就能够唯一构造出这棵树。需要注意的是如果只给定前序遍历和后续遍历，虽然也能构造出一棵树，但不唯一。
其原理为：由于前序遍历的特点为先遍历根节点，再遍历左儿子，最后遍历右儿子。因此通过前序遍历/后序遍历可以知道根节点(整棵树的根节点以及子树的根节点)，再通过中序遍历可以知道根节点的左子树和右子树。这样我们就能够唯一确定这棵树。比如给定某棵树的前序遍历集合为[3,4,5,7,9,10],再给定其中序遍历集合为[4,5,3,7,10,9].
首先，通过前序遍历集合可以知道3是根节点，再定位到中序遍历集合中，4、5是它的左子树；7、10、9是它的右子树。因为前序遍历集合中4在5前，因此4才是3的左儿子；7在10和9前，因此它是3的右儿子。这样不断重复操作，最终还原这棵二叉树
实现代码
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 {
private Map<Integer,Integer>indexMap = new HashMap<>();
private int n;
public TreeNode buildTree(int[] preorder, int[] inorder) {
n = preorder.length;
for(int i = 0; i < n; i ++){
indexMap.put(inorder[i],i);
}
TreeNode root = dfs(preorder,inorder,0,n-1,0,n-1);
return root;
}
public TreeNode dfs(int preorder[],int inorder[],int preorder_left,int preorder_right,int inorder_left,int inorder_right){
if(preorder_left > preorder_right){
return null;
}
int rootVal = preorder[preorder_left];
TreeNode root = new TreeNode(rootVal);
int rootIndexInorder = indexMap.get(rootVal);
int size_left = rootIndexInorder - inorder_left;
int size_right = inorder_right - rootIndexInorder;
root.left = dfs(preorder,inorder,preorder_left + 1,preorder_left + size_left,inorder_left,rootIndexInorder - 1);
root.right = dfs(preorder,inorder,preorder_left + 1 + size_left,preorder_right,rootIndexInorder + 1,inorder_right);
return root;
}
}
|
如果给定的是后序遍历集合和中序遍历集合，那么根节点是post_right,且由于后续遍历的规则为“左右根”，我们需要通过右子树的大小确定左右子树中的元素。
题目见LeetCode106
实现代码
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
| class Solution {
Map<Integer,Integer>postorderIndexOfInorder;
public TreeNode buildTree(int[] inorder, int[] postorder) {
int n = postorder.length;
postorderIndexOfInorder = new HashMap<>();
for(int i = 0; i < n; i ++){
postorderIndexOfInorder.put(inorder[i],i);
}
return dfs(postorder,inorder,0,n-1,0,n-1);
}
public TreeNode dfs(int postorder[],int inorder[],int postorder_left,int postorder_right,int inorder_left,int inorder_right){
if(postorder_left > postorder_right){
return null;
}
int rootVal = postorder[postorder_right];
int index = postorderIndexOfInorder.get(rootVal);
TreeNode root = new TreeNode(rootVal);
int size_left = index - inorder_left;
int size_right = inorder_right - index;
root.right = dfs(postorder,inorder,postorder_right-size_right,postorder_right-1,index+1,inorder_right);
root.left = dfs(postorder,inorder,postorder_left,postorder_right-1-size_right,inorder_left,index-1);
return root;
}
}
|
LeetCode437
这道题给定一个目标值，要求我们求出给定二叉树路径和为目标值的路径数量。需要注意的是，这里的路径并不是指从根节点到叶子节点，而是任意一个及以上节点形成且只能由父节点指向子节点的路径。比如：
在这棵树中：3是一条路径，3->4是一条路径，4->5是一条路径，但是4->3->7不是路径。
其解决方案是利用前缀和的思想，两个节点的前缀和之差就是这两个节点之间的路径和。但仅依靠前缀和还比较麻烦，因为我们需要枚举这两个节点，需要维护两个自由度。但是这道题规定了路径只能由父节点指向子节点，可以转化为给定一个数组和一个目标值，0 < i < j < n，求满足arr[i] + arr[j] = target的索引对的数量，比较暴力的做法是两重循环枚举，但更巧妙的做法是用一个哈希表记录这些数出现的数量，这样只需遍历一次。
由于规定了路径只能由父节点指向子节点，因此当遍历完当前节点后，需要执行恢复操作。比如以上述二叉树为例，当遍历完节点4后，接着会遍历节点7，为了消除节点4的影响，必须从哈希表中减去它的前缀和。
实现代码：
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
|
class Solution {
private int ans = 0;
private Map<Long,Integer>prefixSum;
public int pathSum(TreeNode root, int targetSum) {
prefixSum = new HashMap<>();
prefixSum.put(0L,1);
dfs(root,targetSum,0);
return ans;
}
public void dfs(TreeNode root,int targetSum,long sum){
if(root == null){
return;
}
sum += (long)root.val;
int cnt = prefixSum.getOrDefault(sum - targetSum,0);
ans += cnt;
cnt = prefixSum.getOrDefault(sum,0);
prefixSum.put(sum,++cnt);
dfs(root.left,targetSum,sum);
dfs(root.right,targetSum,sum);
cnt = prefixSum.getOrDefault(sum,0);
prefixSum.put(sum,--cnt);
}
}
|
LeetCode2476
给定一棵二叉搜索树，所谓二叉搜索树是一棵特殊的二叉树，需要满足以下条件：
root.val > root.left.val; root.val < root.right.val.再给定对于一个数，要求在这棵树中找到大于等于这个数的最小值max以及小于等于这个数的最大值min。我的思路就是直接根据搜索二叉树的性质直接遍历两次二叉树，分别找到max和min。在一般情况下，其时间复杂度为log(n),是可以通过的，但是本题有一个特殊样例，该二叉树是一条链，其时间复杂度为O(n),会超时。
提到搜索二叉树，一定要想到中序遍历。因为搜索二叉树经过中序遍历得到的结果是一个严格递增的序列，这往往是一个突破口。而一般看到题中求解最大值最小，最小值最大，一般可以使用二分进行求解。二分有两种模板，向左寻找的模板可以得到第一个大于等于目标值的数(还有一种特殊情况，整个数组中的数都小于目标值)；向右寻找的模板可以得到第一个小于等于目标值的数(还有一种特殊情况，整个数组中的数都大于目标值)。而这两个数分别对应大于等于目标值的最小值和小于等于目标值的最大值。而二分的时间复杂度是确定的log(n),最后一个样例也能通过。
LeetCode2673
要使得所有叶子节点到根节点的路径和相等，不妨先考虑让互为兄弟的叶子节点到根节点的路径和相等需要的最少操作数。因为这两个叶子节点是兄弟节点，所以它们到根节点之间的cost都一样，因此只需要保证这两个叶子节点的cost一样即可，达到这个目的的最小操作数就是让cost等于它们中较大的那个数。接着使用同样的思路考虑其父节点。
例如：
从最后一个非叶子节点开始枚举(对于一棵满二叉树，节点个数/2为最后一个非叶子节点的编号)。其左儿子cost为3，右儿子cost为4，因此让它们的cost等于较大的数4，cost[3] = 5 + 4 = 9.节点2的左儿子cost为2，右儿子cost为4，它们最终的cost为4，cost[2] = 4 + 4 = 8.于是转化为求让这样一棵满二叉树所有叶子节点到根节点的路径和相等的最小操作数。
LCR145
本题要求判断一棵二叉树是否为对称二叉树，核心解题思路就是判断左子树的左儿子的值是否等于右子树的右儿子的值。需要特判边界情况，即left以及right等于null时的情况，如果两者同时到达null，说明这棵二叉树对称，否则这棵二叉树不对称。
实现代码：
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public boolean checkSymmetricTree(TreeNode root) {
return root == null || recur(root.left,root.right);
}
public boolean recur(TreeNode left, TreeNode right){
if(left == null && right == null)return true;
if(left == null || right == null || left.val != right.val)return false;
return recur(left.left,right.right) && recur(left.right,right.left);
}
}
|