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

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

● 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

递归三部曲

1. 函数自身
2. 终止条件
   
3. 递归
   
   

如图：

代码：

/*** 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;}}
}

这篇关于补-代码随想录第21天|● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---