530. Minimum Absolute Difference in BST
Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
Example 1:
Input: root = [4,2,6,1,3]
Output: 1
Example 2:
Input: root = [1,0,48,null,null,12,49]
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[2, 104]. 0 <= Node.val <= 105
最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。
class Solution {
TreeNode pre;// 记录上一个遍历的结点
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root == null)return 0;
traversal(root);
return result;
}
public void traversal(TreeNode root){
if(root == null)return;
//左
traversal(root.left);
//中
if(pre != null){
result = Math.min(result,root.val - pre.val);
}
pre = root;
//右
traversal(root.right);
}
}
For Future References
题目链接：https://leetcode.com/problems/minimum-absolute-difference-in-bst/
文章讲解：https://programmercarl.com/0530.二叉搜索树的最小绝对差.html
501. Find Mode in Binary Search Tree
Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.
If the tree has more than one mode, return them in any order.
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than or equal to the node's key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [1,null,2,2]
Output: [2]
Example 2:
Input: root = [0]
Output: [0]
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. 105 <= Node.val <= 105
Follow up:
Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
搜索树，它中序遍历就是有序的。
弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。
而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。
class Solution {
ArrayList<Integer> resList;
int maxCount;
int count;
TreeNode pre;
public int[] findMode(TreeNode root) {
resList = new ArrayList<>();
maxCount = 0;
count = 0;
pre = null;
findMode1(root);
int[] res = new int[resList.size()];
for (int i = 0; i < resList.size(); i++) {
res[i] = resList.get(i);
}
return res;
}
public void findMode1(TreeNode root) {
if (root == null) {
return;
}
findMode1(root.left);
int rootValue = root.val;
// 计数
if (pre == null || rootValue != pre.val) {
count = 1;
} else {
count++;
}
// 更新结果以及maxCount
if (count > maxCount) {
resList.clear();
resList.add(rootValue);
maxCount = count;
} else if (count == maxCount) {
resList.add(rootValue);
}
pre = root;
findMode1(root.right);
}
}
For Future References
题目链接：https://leetcode.com/problems/find-mode-in-binary-search-tree/
文章讲解：https://programmercarl.com/0501.二叉搜索树中的众数.html
236. Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[2, 105]. 109 <= Node.val <= 109- All
Node.valare unique. p != qpandqwill exist in the tree.
如果left 和 right都不为空，说明此时root就是最近公共节点
如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之依然。
如果left和right都为空，则返回left或者right都是可以的，也就是返回空。
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 && right != null) { // 若找到一个节点
return right;
}else if(left != null && right == null) { // 若找到一个节点
return left;
}else { // 若找到两个节点
return root;
}
}
}
For Future References
题目链接：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
文章讲解：https://programmercarl.com/0236.二叉树的最近公共祖先.html
标签：right,return,21,随想录,TreeNode,null,root,Day,left From： https://www.cnblogs.com/bluesociety/p/16777962.html