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

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

           var getMinimumDifference = function (root) {//中序遍历法：左中右let res = []if (!root) return res;const st = [root] //栈，pop(),push()while (st.length) {let x = st.pop()if (!x) {res.push(st.pop().val)continue}if (x.right) st.push(x.right)st.push(x)st.push(null)if (x.left) st.push(x.left)}//中序遍历先把res求出来，然后求出相邻最小值let m = 100000for (let i = 1; i < res.length; i++) {m = (m <= Math.abs(res[i] - res[i - 1]) ? m : Math.abs(res[i] - res[i - 1]))}return m};

思想

中序遍历，二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。

在过程中记录

var getMinimumDifference = function (root) {//中序遍历法：左中右// let res=[]if(!root) return 0;let prelet curlet m=53453434const st=[root] //栈，pop(),push()while(st.length){let x = st.pop()  if(!x){  //如果x为nullcur = st.pop().valm=(m<=Math.abs(cur-pre)?m:Math.abs(cur-pre))pre = curcontinue}if(x.right) st.push(x.right)st.push(x)st.push(null)if(x.left) st.push(x.left)}return m};

重点

cur = st.pop().val
m=(m<=Math.abs(cur-pre)?m:Math.abs(cur-pre))
pre = cur
cur和pre

501.二叉搜索树中的众数

  /*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number[]}*/var findMode = function (root) {let mapObj = new Map();if (!root) return [];if (!root.left && !root.right) return [root.val]let x = rootlet st = []while (st.length || x) { //只要有一个条件成立while (x) {   //一直把左边的孩子扫入，注意条件，先判断x是否为null，然后在x=x.left(即进入循环的x一定有左孩子st.push(x)x = x.left}//左孩子没了，弹出中x = st.pop()mapObj.set(x.val, (mapObj.get(x.val) || 0) + 1)//把右当做根节点x = x.right}let c = Math.max(...mapObj.values())//得到最大值mapObj = [...mapObj]let res = []for (let i = 0; i < mapObj.length; i++) {if (mapObj[i][1] === c)res.push(mapObj[i][0])}return res};

第一想法

就是遍历（随便用什么方法（迭代，调用都行）），map存储，然后找到最大值，for循环找到，这种方法，真的是很烂了，没有运用搜索树的性质。
我用的是中序迭代，但我这种方法没有用。但中序出来的数组是有顺序的

接下来是卡哥的做法（慢慢体会吧）：

var findMode = function(root) {// 不使用额外空间，使用中序（左中右）遍历,设置出现最大次数初始值为1  let count = 0,maxCount = 1;let pre = root,res = [];// 1.确定递归函数及函数参数const travelTree = function(cur) {// 2. 确定递归终止条件if(cur === null) {return ;}travelTree(cur.left);// 3. 单层递归逻辑if(pre.val === cur.val) {count++;   }else {count = 1;}pre = cur;  //cur是新来的if(count === maxCount) {res.push(cur.val);}if(count > maxCount) {res = [];   //清空res,我之前想的是pop，感觉不行，遂放弃maxCount = count;res.push(cur.val);}travelTree(cur.right);}travelTree(root);return res;
};

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

var lowestCommonAncestor = function(root, p, q) {// 使用递归的方法// 需要从下到上，所以使用后序遍历// 1. 确定递归的函数const travelTree = function(root,p,q) {// 2. 确定递归终止条件if(root === null || root === p || root === q) { //1 5 6 节点return root;}// 3. 确定递归单层逻辑let left = travelTree(root.left,p,q);let right = travelTree(root.right,p,q);if(left !== null && right !== null) {  //7节点返回7return root;}if(left === null) {  //10节点return right;}return left;  //8  4  15 20节点}return  travelTree(root,p,q);
};

第一想法

后序（左右中）递归遍历，想的是找到一个l=true,找到另一个r=true，然后记录，马上结束，看了解析，好像不能

思想

+回溯