代码随想录 Day21 - 二叉树(七)
作者:jjn0703
- 2023-07-19 江苏
本文字数:1741 字
阅读完需:约 6 分钟
530. 二叉搜索树的最小绝对差
二叉搜索树,双指针遍历,咋有点想到之前做的反转链表。中序遍历递归解法可太秀了。
/**
* Definition for a binary tree node.
* 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;
* }
* }
*/
class Solution {
private TreeNode pre;
private int minDifference;
public int getMinimumDifference(TreeNode root) {
this.minDifference = Integer.MAX_VALUE;
traversal(root);
return minDifference;
}
private void traversal(TreeNode current) {
if (current == null) {
return;
}
traversal(current.left);
if (pre != null) {
minDifference = Math.min(minDifference, current.val - pre.val);
}
pre = current;
traversal(current.right);
}
}
复制代码
501. 二叉搜索树中的众数
一次遍历,解决问题,很难想到的了,当然必须是二叉搜索树才可以这样做。
/**
* Definition for a binary tree node.
* 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;
* }
* }
*/
class Solution {
private List<Integer> result;
private int maxCount;
private int curCount;
private TreeNode pre;
public int[] findMode(TreeNode root) {
this.result = new ArrayList<>();
traversal(root);
int[] res = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
res[i] = result.get(i);
}
return res;
}
private void traversal(TreeNode current) {
if (current == null) {
return;
}
traversal(current.left);
if (result.isEmpty() && maxCount == 0) {
result.add(current.val);
}
int curVal = current.val;
if (pre == null || curVal != pre.val) {
curCount = 1;
} else {
curCount++;
}
if (curCount > maxCount) {
result = new ArrayList<>();
result.add(curVal);
maxCount = curCount;
} else if (curCount == maxCount) {
result.add(curVal);
}
pre = current;
traversal(current.right);
}
}
复制代码
236. 二叉树的最近公共祖先
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) { // 递归结束条件
return root;
}
// 后序遍历
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null && right == null) { // 若未找到节点 p 或 q
return null;
} else if (left == null) { // 若找到一个节点
return right;
} else if (right == null) { // 若找到一个节点
return left;
} else { // 若找到两个节点
return root;
}
}
}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 4
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/5ceaa92bbaf602120be6b5e15】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论