台州网站怎么推广,重庆建筑人才网官网,html网页制作基础知识,购物商城平台开发第六章 二叉树part06
详细布置
530.二叉搜索树的最小绝对差
需要领悟一下二叉树遍历上双指针操作#xff0c;优先掌握递归 题目链接/文章讲解#xff1a;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%B…第六章 二叉树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 prenull;int minInteger.MAX_VALUE;public int getMinimumDifference(TreeNode root) {if(root null ) return 0;recursion(root);return min;}public void recursion(TreeNode root){if(rootnull){return;}recursion(root.left);if(pre!nullMath.abs(root.val-pre.val)min){minMath.abs(root.val-pre.val);}preroot;recursion(root.right);}501.二叉搜索树中的众数
题目链接 https://leetcode.cn/problems/find-mode-in-binary-search-tree/ 解题思路 中序遍历相邻要考虑如何更新当前和前一个相同count; code ArrayListInteger resList;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {if(rootnull){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(rootnull){return;}recursion(root.left);int rootValueroot.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(rootnull){return null;}//等与p或q返回给上层的递归函数if(rootp||rootq){return root;}//单层递归逻辑left或right要么是null要么是p或qTreeNode leftlowestCommonAncestor(root.left,p,q);TreeNode rightlowestCommonAncestor(root.right,p,q);//处理中的逻辑//left和right都不等于null那么一定包含了p和q 这个root的节点就是最近的公共祖先if(left!nullright!null){return root;}//left 找到了p或q节点回溯给上一层if(left!null){return left;}//right 找到了p或q节点回溯给上一层if(right!null){return right;}//这里是left和right都等于null那么返回nullreturn null;}
