617.合并二叉树
力扣题目链接
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
解决思路
- 如果树节点为空，则用另一颗树的节点。
Java实现
class Solution_LC617 {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
int val = root1.val + root2.val;
TreeNode root = new TreeNode(val);
root.left = mergeTrees(root1.left, root2.left);
root.right = mergeTrees(root1.right, root2.right);
return root;
}
}
700.二叉搜索树中的搜索
力扣题目地址
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
解决思路
二叉搜索树是一个有序树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树
- 当root的值>指定的值，从左子树上尝试获取；否则从右子树上获取
- 当root的值>指定的值，左子树上都是比root的值小的，右子树上都是比root的值大的。
Java实现
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (root.val > val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
}
98.验证二叉搜索树
力扣题目链接
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
输入：root = [2,1,3]
输出：true
解决思路
- 构建新的递归函数，不断更新上限值和下限值。
- 中序遍历，不断比较节点
- 中序遍历，构成数组比较。
Java实现
递归实现
class Solution {
public boolean isValidBST(TreeNode root) {
return validBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validBST(TreeNode root, long lower, long upper) {
if (root == null) {
return true;
}
if (root.val <= lower || root.val >= upper) return false;
return validBST(root.left, lower, root.val) && validBST(root.right, root.val, upper);
}
}
中序遍历，左中右
class Solution_LC98_II {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
long inorder = Long.MIN_VALUE;
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (cur.val <= inorder) {
return false;
}
inorder = cur.val;
cur = cur.right;
}
return true;
}
}
530.二叉搜索树的最小绝对差
力扣题目链接
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
输入：root = [4,2,6,1,3]
输出：1
解决思路
- 因为要获取最小值，result的初始值设置为最大。
- 使用中序遍历。
Java实现
class Solution {
public int getMinimumDifference(TreeNode root) {
int res = Integer.MAX_VALUE;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode pre = null;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (pre != null) {
res = Math.min(cur.val - pre.val, res);
}
pre = cur;
cur = cur.right;
}
return res;
}
}
501.二叉搜索树中的众数
力扣题目链接
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
输入：root = [1,null,2,2]
输出：[2]
解题思路
- 使用中序遍历，去挨个遍历二叉树上的元素。如果当前元素和前一个元素一致，计数+1。
- 使用全局变量，记录当前元素的次数；最大的次数。
Java实现
使用递归的方式
class Solution_LC501 {
List<Integer> answers = new ArrayList<>();
int base, count, maxCount;
public int[] findMode(TreeNode root) {
dfs(root);
int[] mode = new int[answers.size()];
for (int i = 0; i < answers.size(); ++i) {
mode[i] = answers.get(i);
}
return mode;
}
private void dfs(TreeNode cur) {
if (cur == null) {
return;
}
dfs(cur.left);
caluate(cur.val);
dfs(cur.right);
}
private void caluate(int val) {
if (val == base) {
count++;
} else {
count = 1;
base = val;
}
if (count == maxCount) {
answers.add(val);
}
if (count > maxCount) {
maxCount = count;
answers.clear();
answers.add(val);
}
}
}
使用中序迭代
class Solution_LC501_II {
List<Integer> answers = new ArrayList<>();
int count, maxCount;
public int[] findMode(TreeNode root) {
TreeNode cur = root;
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (pre == null) {
count = 1;
} else if (pre.val == cur.val) {
count++;
} else {
count = 1;
}
if (count == maxCount) {
answers.add(cur.val);
}
if (count > maxCount) {
maxCount = count;
answers.clear();
answers.add(cur.val);
}
pre = cur;
cur = cur.right;
}
int[] mode = new int[answers.size()];
for (int i = 0; i < answers.size(); ++i) {
mode[i] = answers.get(i);
}
return mode;
}
}
236. 二叉树的最近公共祖先
力扣题目链接
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
解题思路
- 如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。
- 在子树上找到p或者q，就可以了。如果p和q分别在两个子树上都可以分别找到，则当前节点是公共祖先。
Java实现
class Solution_LC236 {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
//后序遍历
TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
if (leftNode == null && rightNode == null) {
return null;
}
if (leftNode == null) {
return rightNode;
}
if (rightNode == null) {
return leftNode;
}
return root;
}
}
235. 二叉搜索树的最近公共祖先
力扣题目链接
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
解题思路
- 公共祖先的节点的值的大小必须大于等于左节点，小于等于右节点。如果当前节点的值比p和q节点的值都要大，可以在左子树上继续寻找，左子树上都是比当前节点小的数据。如果当前节点的值比p和q的节点都要小的话，在右子树上寻找。
Java实现
递归方式
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
}
非递归方式
public class Solution_LC235_II {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (true) {
if (root.val > p.val && root.val > q.val) {
root = root.left;
} else if (root.val < p.val && root.val < q.val) {
root = root.right;
} else {
break;
}
}
return root;
}
}
