代码随想录 day 18 二叉树

第六章 二叉树part06

详细布置

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

需要领悟一下二叉树遍历上双指针操作，优先掌握递归
题目链接/文章讲解：https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html
视频讲解：https://www.bilibili.com/video/BV1DD4y11779

501.二叉搜索树中的众数

和 530差不多双指针思路，不过 这里涉及到一个很巧妙的代码技巧。
可以先自己做做看，然后看我的视频讲解。
https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html
视频讲解：https://www.bilibili.com/video/BV1fD4y117gp

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

本题其实是比较难的，可以先看我的视频讲解
https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
视频讲解：https://www.bilibili.com/video/BV1jd4y1B7E2

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

题目链接

https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/

解题思路

还是二叉搜索的中序遍历单调递增的特性，判断相邻俩个节点的差值的绝对值和最小值比较，最终求出最小值
递归误区：想着直接在getMinimumDifference函数进行递归，但是遇到空节点 返回int的值是什么？ 发现终止条件确定不下来，所以要重新考虑递归函数的参数和返回值。
这时考虑到新建递归函数，遇到null节点return ，递归函数返回值是void，参数就是节点，因为每次操作的全局变量就是结果，不需要返回值。

code

    private TreeNode pre=null;int min=Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {if(root ==null ) return 0;recursion(root);return min;}public void recursion(TreeNode root){if(root==null){return;}recursion(root.left);if(pre!=null&&Math.abs(root.val-pre.val)<min){min=Math.abs(root.val-pre.val);}pre=root;recursion(root.right);}

501.二叉搜索树中的众数

题目链接

https://leetcode.cn/problems/find-mode-in-binary-search-tree/

解题思路

中序遍历相邻，要考虑如何更新，当前和前一个相同，count++;

code

    ArrayList<Integer> resList;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {if(root==null){return null;}resList = new ArrayList<>();maxCount = 0;count = 0;pre = null;recursion(root);int[] res = new int[resList.size()];for (int i = 0; i < resList.size(); i++) {res[i] = resList.get(i);}return res;}public void recursion(TreeNode root){if(root==null){return;}recursion(root.left);int rootValue=root.val;// 计数if (pre == null || rootValue != pre.val) {count = 1;} else {count++;}// 更新结果以及maxCountif (count > maxCount) {resList.clear();resList.add(rootValue);maxCount = count;} else if (count == maxCount) {resList.add(rootValue);}pre = root;recursion(root.right);}

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

题目链接

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

解题思路

后序遍历的回溯过程
如果p节点下有q这种情况，代码已经包含了这种逻辑，就是递归终止条件如果遇到p就是直接返回p，根本不用向下递归是否有q了，题目说了一定有p和q节点，所以最后的回溯到第一层后最近公共祖先就是p。

code

    //后序遍历回溯的思想，把找到的p和q向上返回，左右中，中的时候判断是否符合public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//1.递归函数的终止条件//等于null返回nullif(root==null){return null;}//等与p或q返回给上层的递归函数if(root==p||root==q){return root;}//单层递归逻辑，left或right要么是null要么是p或qTreeNode left=lowestCommonAncestor(root.left,p,q);TreeNode right=lowestCommonAncestor(root.right,p,q);//处理中的逻辑//left和right都不等于null，那么一定包含了p和q ，这个root的节点就是最近的公共祖先if(left!=null&&right!=null){return root;}//left 找到了p或q节点，回溯给上一层if(left!=null){return left;}//right 找到了p或q节点，回溯给上一层if(right!=null){return right;}//这里是left和right都等于null，那么返回nullreturn null;}