代码随想录算法训练营第15天|530.二叉搜索树的最小绝对差，501.二叉搜索树中的众数，236.二叉树的最近公共祖先

530. 二叉搜索树的最小绝对差看到题目的第一想法如果列成数组去计算绝对差应该也不难但是不知道递归求差应该怎么做看完代码随想录的第一想法感觉跟上一题98.验证二叉搜索树很相似上一题存的是最大值去比较这道题存的是上一节点去比较用自己的话描述根据上一题的做题思路利用递归的过程存下上一个递归的节点然后让当前节点和上一个递归的节点比较得出他们之间的差值进行下一次的比较代码/** * 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; * } * } */classSolution{privateTreeNodeprenull;privateintresultInteger.MAX_VALUE;publicintgetMinimumDifference(TreeNoderoot){findTreeNode(root);returnresult;}publicvoidfindTreeNode(TreeNoderoot){if(rootnull){return;}findTreeNode(root.left);if(pre!null){resultMath.min(result,root.val-pre.val);}preroot;findTreeNode(root.right);}}实现过程中遇到哪些困难无今日收获记录一下自己的学习时长熟悉了二叉搜索树的使用 14.02-15.00501. 二叉搜索树中的众数看到题目的第一想法想不到怎么去解这道题目看完代码随想录的第一想法不用二叉搜索树的做法就全遍历一遍翻入Map然后再转成数组进行排序最后得出结果用二叉搜索树的做法跟上一题 二叉树搜索树的最小绝对差 一样都要定义一个前一个节点的指针然后一直累计这个一样的数在二叉搜索树中众数一定是相邻的用自己的话描述看注释吧代码/** * 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; * } * } */classSolution{TreeNodepre;intcount;intmaxCount;ArrayListIntegerresList;publicint[]findMode(TreeNoderoot){//递归三部曲//1.找到递归参数和返回值//2.找到递归的终止条件//3.找到递归的单层遍历是什么//要记录前节点用中序遍历//1.递归参数是当前节点没有返回值因为不需要判断什么只需要遍历完一遍整个二叉搜索树//2.当遇到空节点就返回//3.递归单层先进行左子树的递归看看当前的值是不是等于上一个节点的值如果不是就设置计算器为1如果是就在计算器上加1//然后再判断计数器是不是大于当前的数值大于的话就重置一下最大值等于的话就加上这个节点的数然后进入右子节点的递归prenull;count0;maxCount0;resListnewArrayList();findTreeMode(root);int[]resnewint[resList.size()];inti0;for(intr:resList){res[i]r;}returnres;}publicvoidfindTreeMode(TreeNoderoot){if(rootnull){return;}findTreeMode(root.left);if(prenull){count1;}elseif(root.valpre.val){count;}else{count1;}if(countmaxCount){resList.clear();resList.add(root.val);maxCountcount;}elseif(countmaxCount){resList.add(root.val);}preroot;findTreeMode(root.right);}}实现过程中遇到哪些困难无今日收获记录一下自己的学习时长二叉搜索树的数如果是一样那就会连续 21.31-22.47236. 二叉树的最近公共祖先看到题目的第一想法感受到了很难想不到有什么解法看完代码随想录的第一想法原来是通过对节点的判断然后找到公共祖先用自己的话描述通过递归遍历整个树然后递归的途中如果遇到指定节点就返回如果左右都是指定节点就返回当前节点算做公共祖先代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){//递归三部曲//1.找到递归参数和返回值//2.找到递归的终止条件//3.找到递归的单层遍历是什么//因为是自底向上找数所以用后序遍历//1.递归参数为当前节点和搜索的节点pq返回值为节点如果只是找到的话返回true就行但是还要返回公共节点于是返回值为节点//2.找到qp或null就返回当前节点//3.先看当前节点是不是为null或指定节点如果是就返回当前节点//然后先将左右子节点先递归回来看看底下有没有指定的节点如果有就返回那一边的节点如果都有那当前节点就是公共祖先返回当前节点if(rootnull||rootp||rootq){returnroot;}TreeNodeleftlowestCommonAncestor(root.left,p,q);TreeNoderightlowestCommonAncestor(root.right,p,q);if(leftnullrightnull){returnnull;}elseif(left!nullrightnull){returnleft;}elseif(leftnullright!null){returnright;}else{returnroot;}}}实现过程中遇到哪些困难不能理解怎么去判断公共祖先今日收获记录一下自己的学习时长对于后序遍历的理解就是需要遍历整个树的时候就需要用到这一点更加深刻了 22.48-23.55