补-代码随想录第21天|● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

本文主要是介绍补-代码随想录第21天|● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

● 530.二叉搜索树的最小绝对差
- 思路一：递归-中序遍历
- - 代码：定义双指针做插值
- 思路二：统一迭代法-速度较慢
● 501.二叉搜索树中的众数
- 思路：
- 代码：
● 236. 二叉树的最近公共祖先
- 思路
- - 情况1
  - 情况2
  - 递归三部曲
- 代码：

● 530.二叉搜索树的最小绝对差

在这里插入图片描述

思路一：递归-中序遍历

在这里插入图片描述

代码：定义双指针做插值

public class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){};TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}TreeNode(int val){this.val=val;}
}
class Solution {int result=Integer.MAX_VALUE;TreeNode pre;//默认为nullpublic 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(Math.abs(root.val-pre.val),result);//不用绝对值，前-后一定递增result=Math.min(root.val-pre.val,result);}pre=root;traversal(root.right);}
}

思路二：统一迭代法-速度较慢

/*** 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 {int result=Integer.MAX_VALUE;TreeNode pre;//默认为nullStack<TreeNode> stack = new Stack<>();public int getMinimumDifference(TreeNode root) {if(root!=null){stack.push(root);}while(!stack.isEmpty()){TreeNode cur=stack.peek();if(cur!=null){stack.pop();if(cur.right != null)//右stack.add(cur.right);stack.add(cur);//中stack.add(null);if(cur.left != null)//左stack.add(cur.left);}else{stack.pop();cur=stack.pop();if(pre!=null)result=Math.min(cur.val-pre.val,result);pre=cur;}}return result;}
}

● 501.二叉搜索树中的众数

在这里插入图片描述

思路：

在这里插入图片描述

代码：

class Solution {int count;ArrayList<Integer> resList;int maxcount;TreeNode pre;public int[] findMode(TreeNode root) {count=1;maxcount=Integer.MIN_VALUE;resList=new ArrayList<>();search(root);int n=resList.size();int[] res=new int[n];for(int i=0;i<n;i++){res[i]=resList.get(i);}return res;}public void search(TreeNode root) {if(root==null)return;search(root.left);if(pre!=null){if(pre.val==root.val){count++;}else{count=1;}}pre=root;if(count==maxcount){resList.add(root.val);}if(count>maxcount){maxcount=count;resList.clear();resList.add(root.val);}search(root.right);}

● 236. 二叉树的最近公共祖先

在这里插入图片描述

思路

在这里插入图片描述

情况1

在这里插入图片描述

情况2

在这里插入图片描述

递归三部曲

函数自身
终止条件
递归

在这里插入图片描述
如图：

代码：

/*** 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){return root;}else if(left==null&&right!=null){return right;}else if(left!=null&&right==null){return left;}else{return null;}}
}