摘要

• 遍历二叉搜索树常用中序遍历，二叉搜索树的中序遍历能得到升序序列。
• 如果二叉搜索树可以含重复值，中序遍历也能得到非降序序列
• 双指针法中序遍历二叉搜索树是常用方法
• 二叉树的后序遍历是天然的回溯过程，可以自底向上的处理二叉树的节点

LeetCode530 二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差 - 力扣（Leetcode）

• 对二叉搜索树进行中序遍历，得到的序列是升序序列。例如，以下这棵二叉搜索树，中序遍历的序列为[1,2,3,4,6]

image.png

• 在升序序列中，两个值离得越远肯定差值越大，最小的绝对差只可能出现在相邻元素的差。所以，只需要通过一次中序遍历，同时求出每组相邻元素的差，即可求得二叉搜索树的最小绝对差。

完整的题解代码如下

class Solution {
public:
    void searchBST(TreeNode* cur, TreeNode*& pre, int& res) {
        if (!cur) return;
        searchBST(cur->left, pre, res);
        if (pre && abs(cur->val - pre->val) < res) {
            res = abs(cur->val - pre->val);
        }
        pre = cur;
        searchBST(cur->right, pre, res);
    }
    int getMinimumDifference(TreeNode* root) {
        TreeNode* pre = nullptr;
        int res = INT_MAX;
        searchBST(root, pre, res);
        return res;
    }
};

LeetCode501 二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（Leetcode）

• 可以包含重复值的二叉搜索树，中序遍历得到得序列是非降序序列。如果我们通过中序遍历，那么重复值一定是在序列中连续出现的，这就给我们统计每个值的出现次数提供了方便。
• 二叉搜索树的中序遍历，关键在于“中”的处理逻辑。
  • 如果一个值出现在中序序列中，将count初始化为1
  • 如果当前节点的值和上一个节点的值相同，则count++
  • 判断count和已遍历的子树的maxCount的大小关系：如果count == maxCount则将当前节点的值加入答案数组；如果count > maxCount则将答案数组清空，再将当前节点的值加入答案数组。

完整的题解代码如下

class Solution {
public:
    void searchBST(TreeNode* cur, TreeNode*& pre, int& count, int& maxCount, vector<int>& res) {
        if (!cur) return;
        searchBST(cur->left, pre, count, maxCount,res);
        if (pre && pre->val == cur->val) count++;
        if (pre && pre->val != cur->val) count = 1;
        if (count > maxCount) {
            res.clear();
            res.push_back(cur->val);
            maxCount = count;
        }
        else if (count == maxCount) {
            res.push_back(cur->val);
        }
        pre = cur;
        searchBST(cur->right, pre, count, maxCount, res);
    }
    vector<int> findMode(TreeNode* root) {
        TreeNode* pre = nullptr;
        int count = 1;
        int maxCount = -1;
        vector<int> res;
        searchBST(root, pre, count, maxCount, res);
        return res;
    }
};

LeetCode236 二叉树的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（Leetcode）

• 初见题目的想法：这道题目要自底向上找最近公共祖先，而遍历二叉树一般只能自顶向下遍历，即从根节点从上往下遍历。那应该怎样找到最近的公共祖先呢？
• 虽然无法从下往上访问二叉树的节点，但是可以从下往上处理二叉树的节点，这对应的是后序遍历。
• 通过后序遍历，可以从下往上返回结果。所以当需要自底向上处理二叉树的节点时，优先考虑后序遍历。
• 既然用后序遍历，递归实现是比较容易实现的：
  • 传入的参数和返回值：传入当前子树的根节点，节点p和节点q；返回值应该能标识是否找到节点p或者q。
  • 递归的终止条件：当前子树的根节点为p或者q，则返回当前子树的根节点；若当前子树的根节点为空，说明这条路径上没有找到p或者q，返回nullptr
  • 单层递归的处理逻辑：采用后序遍历，所以先去左子树寻找p或者q，再去右子树寻找p或者q；如果在左子树和右子树中分别找到了p和q，说明当前节点是p和q的公共祖先，则返回当前子树的根节点；如果只在左子树中找到了p或q的其中一个，则返回左子树的根节点，右子树同理。
• 由于是自底向上返回查找p和q的结果，所以找到的第一个p和q的公共祖先，也是p和q的最近公共祖先。

完整的题解代码如下

class Solution {
public:
    TreeNode* traversal(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;
        if (root == p || root == q) return root;
        
        TreeNode* left = traversal(root->left, p, q);
        TreeNode* right = traversal(root->right, p, q);

        if (left && !right) return left;
        if (!left && right) return right;
        if (left && right) return root;
        return nullptr;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return traversal(root, p, q);
    }
};