Follow Carl To Grow|【LeetCode】530.二叉搜索树的最小绝对差，501.二叉搜索树中的众数，236. 二叉树的最近公共祖先

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

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

思路：中序遍历拿到递增序列，然后求相邻两个数最小值即可。也可以在遍历过程中就拿到这个最小值，此时需要用指针记录上一个节点。

代码A：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> m_val;
    void inOrder(TreeNode* root)
    {
        if (!root)
        {
            return;
        }
        if (root->left)
        {
            inOrder(root->left);
        }
        m_val.push_back(root->val);        
        if (root->right)
        {
            inOrder(root->right);
        }
    }

    int getMinimumDifference(TreeNode* root) {
        inOrder(root);
        int minval = INT_MAX;
        for (int i = 0; i <m_val.size() - 1; ++i)
        {
            int val = m_val[i + 1] - m_val[i];
            minval = min(minval, val);
        }
        return minval;
    }
};

代码B：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minVal = INT_MAX;
    TreeNode* pre = NULL;
    void inOrder(TreeNode* root)
    {
        if (!root)
        {
            return;
        }
        inOrder(root->left);

        if (pre)
        {
            minVal = min(minVal, root->val - pre->val);
        }
        pre = root;

        inOrder(root->right);
    }

    int getMinimumDifference(TreeNode* root) {
        inOrder(root);
        return minVal;
    }
};

【LeetCode】501.二叉搜索树中的众数

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

思路：第一想法是用map存储所有<val, count>，然后以count进行排序即可。发现是二叉搜索树，想办法用上中序递增的性质，用一个指针记录前一个结点。如果值相同则出现频率增加，如果出现频率超过最大出现频率则更新数组，如果出现频率等于最大出现频率则追加到数组。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> m_val;
    int m_curNum = 0, m_maxNum = 0;
    TreeNode* m_pre = NULL;

    void inOrder(TreeNode* root)
    {
        if (!root)
        {
            return ;
        }

		// 左
        if (root->left)
        {
            inOrder(root->left);
        }

		// 中
        if (!m_pre)
        {
            m_curNum = 1;
        }
        else if (m_pre->val == root->val)
        {
            m_curNum++;
        }
        else
        {
            m_curNum = 1;
        }
        m_pre = root;
        if (m_curNum == m_maxNum)
        {
            m_val.push_back(root->val);
        }
        else if (m_curNum > m_maxNum)
        {
            m_maxNum = m_curNum;
            m_val.clear();
            m_val.push_back(root->val);
        }

		// 右
        if (root->right)
        {
            inOrder(root->right);
        }
    }

    vector<int> findMode(TreeNode* root) {
        if (!root)
        {
            return m_val;
        }
        inOrder(root);
        return m_val;
    }
};

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

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

思路：根结点肯定是公共祖先，自己也肯定是自己的祖先。要求最近公共祖先，应该自底向上进行遍历，对应到二叉树里只有后序遍历。后序遍历先处理左右子树，然后处理中间结点，是天然的回溯过程。可以根据左子树求出的最近公共祖先和右子树求出的最近公共祖先判断，谁不为空值就返回谁，都不为空值则返回中间。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q)
        {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (!left && !right)
        {
            return NULL;
        }
        else if (!left)
        {
            return right;
        }
        else if (!right)
        {
            return left;
        }
        else
        {
            return root;
        }   
    }
};

心态：“第六章 二叉树 part07” 拿下！
参考资料