LeetCode-20200821-20200927
程序员文章站
2022-07-08 20:23:20
...
钥匙和房间
-
题目。把二叉搜索树转换为累加树。给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree -
思路。给定的是一个二叉搜索树，我们知道二叉搜索树的中序遍历结果是一个非递减的序列。因此我们可以先遍历一遍树，得到所有节点的和。然后再中序遍历树，遍历时不断修改当前节点的值即可。
-
代码。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int sum;
public TreeNode convertBST(TreeNode root) {
if (root == null) {
return root;
}
sum = getSum(root);
traversal(root);
return root;
}
private void traversal(TreeNode root) {
if (root == null) {
return;
}
traversal(root.left);
int tmp = root.val;
root.val = sum;
sum -= tmp;
traversal(root.right);
}
private int getSum(TreeNode root) {
if (root == null) {
return 0;
}
return getSum(root.left) + getSum(root.right) + root.val;
}
}
监控二叉树
- 题目。给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。https://leetcode-cn.com/problems/binary-tree-cameras/ - 思路。首先这道题是比较有意思的，不是常规的遍历树的问题。对于每个节点，我们可以选择放或者不放相机。如果当前节点放相机，则它的left和right上可以不放（当然也可以放）；如果当前节点不放相机，那么它的left和right至少有一个需要放置相机。我们取二者的较小值即可。
- 代码。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minCameraCover(TreeNode root) {
if (root == null) {
return 0;
}
int[] res = dfs(root);
return res[1];
}
/**
* 遍历过程中返回三个信息，
* arr[0]表示以root为根，并且在root处放置一个相机时，放置的最少相机数量
* arr[1]表示以root为根，放置的最少照相机的数量
* arr[2]表示以root为根，覆盖两棵子树需要的摄像头数目，无论root本身是否被监控到
*/
private int[] dfs(TreeNode root) {
if (root == null) {
return new int[]{Integer.MAX_VALUE / 2, 0, 0};
}
int[] left = dfs(root.left);
int[] right = dfs(root.right);
int[] res = new int[3];
// root处必须放一个，左子树和右子树保证自己被覆盖即可
res[0] = 1 + left[2] + right[2];
// root处放和不放相机，取最小值。
// 1. root处放相机的值是res[0]；
// 2. 如果root处不放，有2.1和2.2两种情况
// 2.1 左子树必须放并且右子树放不放都行，即为left[0]+ right[1]
// 2.2 右子树必须放并且左子树放不放都行，即为right[0] + left[1]
res[1] = Math.min(res[0], Math.min(left[0] + right[1], right[0] + left[1]));
// 如果以root为根的整个子树都被覆盖了，那么root的左右两个子树一定被覆盖了
// 左右两个子树也可以选择自己覆盖自己
res[2] = Math.min(res[0], left[1] + right[1]);
return res;
}
}
合并二叉树
-
题目。给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees -
思路。如果t1是空则返回t2；如果t2是空则返回t1；二者都不是空，则创建一个新的节点，并递归设置left和right。
-
代码。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return null;
}
if (t1 == null) {
return t2;
}
if (t2 == null) {
return t1;
}
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}
}
二叉搜索树中的众数
- 题目。
- 思路。
- 代码。
合并二叉树
-
题目。给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。要求额外空间复杂度是O(1)。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree -
思路。显然我们需要遍历二叉树，而如果想使用额外空间复杂度是O(1)来遍历二叉树，那么可以使用Morris遍历。Morris遍历的思想是利用叶子节点的right指针来回到父节点。另外，由于给定的是一个二叉搜索树，所以中序遍历的结果是一个非递减的序列，我们可以利用这一点来得到众数。
-
代码。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int base;
private int count;
private int maxCount;
private List<Integer> res = new ArrayList<>();
public int[] findMode(TreeNode root) {
if (root == null) {
return new int[]{};
}
TreeNode cur1 = root;
TreeNode cur2 = null;
while (cur1 != null) {
cur2 = cur1.left;
if (cur2 != null) {
// 让cur2走到cur1左子树的最右节点
while (cur2.right != null && cur2.right != cur1) {
cur2 = cur2.right;
}
if (cur2.right == null) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
}
}
update(cur1.val);
cur1 = cur1.right;
}
int[] resArray = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
resArray[i] = res.get(i);
}
return resArray;
}
public void update(int cur) {
if (cur == base) {
count++;
} else {
count = 1;
base = cur;
}
if (count == maxCount) {
res.add(cur);
}
if (count > maxCount) {
res.clear();
res.add(cur);
maxCount = count;
}
}
}
从中序与后序遍历序列构造二叉树
- 题目。根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ - 思路。显然是一个递归的过程。后序序列的最后一个节点是整个树的根节点。在中序序列中，根节点左侧的节点是左子树，根节点右侧的树是右子树。在后序序列中，左子树的长度和中序序列中的左子树长度是一样的，右子树同理。也就是下面代码中// index - 1 - i = k - p -> k = p + index - 1 - i
- 代码。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || inorder.length == 0 || postorder == null || postorder.length == 0) {
return null;
}
Map<Integer, Integer> node2IndexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
node2IndexMap.put(inorder[i], i);
}
int len = postorder.length;
return f(inorder, 0, len - 1, postorder, 0, len - 1, node2IndexMap);
}
private TreeNode f(int[] inorder, int i, int j, int[] postorder, int p, int q, Map<Integer, Integer> node2IndexMap) {
if (i == j) {
return new TreeNode(inorder[i]);
}
if (i > j) {
return null;
}
TreeNode root = new TreeNode(postorder[q]);
int index = node2IndexMap.get(postorder[q]);
// index - 1 - i = k - p -> k = p + index - 1 - i
root.left = f(inorder, i, index - 1, postorder, p, p + index - 1 - i, node2IndexMap);
root.right = f(inorder, index + 1, j, postorder, p + index - i, q - 1, node2IndexMap);
return root;
}
}
路径总和 II
-
题目。给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
- 思路。回溯求解即可。
- 代码。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
f(root, new ArrayList<>(), 0, sum, res);
return res;
}
private void f(TreeNode curNode, List<Integer> curList, int curSum, int target, List<List<Integer>> res) {
if (curNode == null) {
return;
}
if (curNode.left == null && curNode.right == null) {
if (curSum + curNode.val == target) {
curList.add(curNode.val);
res.add(new ArrayList<>(curList));
curList.remove(curList.size() - 1);
return;
}
}
curList.add(curNode.val);
f(curNode.left, curList, curSum + curNode.val, target, res);
f(curNode.right, curList, curSum + curNode.val, target, res);
curList.remove(curList.size() - 1);
}
}
上一篇： 维吉尼亚密码解密
下一篇： OpenSSL CentOS 7 安装