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

题目：

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例：

输入：root = [4,2,6,1,3]
输出：1

解题思路：

二叉搜索树的中序遍历是有序的，因此可以使用双指针来依次记录最小值。

var getMinimumDifference = function (root) {
    let result = Infinity;
    let pre = null;
    const traversal = (cur) => {
        if (cur === null) {
            return;
        }
        traversal(cur.left);
        if (pre !== null) {
            result = Math.min(result, cur.val - pre.val);
        }
        pre = cur;
        traversal(cur.right);
    }
    traversal(root);
    return result;
};

501. 二叉搜索树中的众数

题目：

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值

• 左子树和右子树都是二叉搜索树
  示例：

  
  

输入：root = [1,null,2,2]
输出：[2]

解题思路：

这道题依然是利用双指针中序遍历来解决。

var findMode = function (root) {
    let pre = null;
    let count = 0;
    let maxCount = 0;
    let result = [];
    const traversal = (cur) => {
        if (cur === null) {
            return;
        }
        traversal(cur.left);
        if (pre === null) {
            count = 1;
        } else if (pre.val === cur.val) {
            count++;
        } else {
            count = 1;
        }
        pre = cur;
        if (count === maxCount) {
            result.push(cur.val)
        }
        if (count > maxCount) {
            maxCount = count;
            result = [];
            result.push(cur.val);
        }
        traversal(cur.right);
    }
    traversal(root);
    return result;
};

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

题目：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

解题思路：

这道题是从下往上遍历所以采用后序遍历。判断逻辑是 如果递归遍历遇到q，就将q返回，遇到p就将p返回，那么如果 左右子树的返回值都不为空，说明此时的中节点，一定是q和p的最近祖先。

var lowestCommonAncestor = function (root, p, q) {
    const traversal = (root, p, q) => {
        if (!root) {
            return root;
        }
        if (root === p || root === q) {
            return root;
        }
        const left = traversal(root.left, p, q);
        const right = traversal(root.right, p, q);
        if (left !== null && right !== null) {
            return root;
        }
        if (left === null && right !== null) {
            return right;
        }
        else if (left !== null && right === null) {
            return left;
        } else {
            return null;
        }
    }
    return traversal(root, p, q);
};