摘要

• 遍歷二叉搜索樹常用中序遍歷，二叉搜索樹的中序遍歷能得到升序序列。
• 如果二叉搜索樹可以含重復值，中序遍歷也能得到非降序序列
• 雙指針法中序遍歷二叉搜索樹是常用方法
• 二叉樹的后序遍歷是天然的回溯過程，可以自底向上的處理二叉樹的節(jié)點

LeetCode530 二叉搜索樹的最小絕對差

530. 二叉搜索樹的最小絕對差 - 力扣（Leetcode）

• 對二叉搜索樹進行中序遍歷，得到的序列是升序序列。例如，以下這棵二叉搜索樹，中序遍歷的序列為[1,2,3,4,6]

image.png

• 在升序序列中，兩個值離得越遠肯定差值越大，最小的絕對差只可能出現(xiàn)在相鄰元素的差。所以，只需要通過一次中序遍歷，同時求出每組相鄰元素的差，即可求得二叉搜索樹的最小絕對差。

完整的題解代碼如下

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 二叉搜索樹中的眾數(shù)

501. 二叉搜索樹中的眾數(shù) - 力扣（Leetcode）

• 可以包含重復值的二叉搜索樹，中序遍歷得到得序列是非降序序列。如果我們通過中序遍歷，那么重復值一定是在序列中連續(xù)出現(xiàn)的，這就給我們統(tǒng)計每個值的出現(xiàn)次數(shù)提供了方便。
• 二叉搜索樹的中序遍歷，關(guān)鍵在于“中”的處理邏輯。
  • 如果一個值出現(xiàn)在中序序列中，將count初始化為1
  • 如果當前節(jié)點的值和上一個節(jié)點的值相同，則count++
  • 判斷count和已遍歷的子樹的maxCount的大小關(guān)系：如果count == maxCount則將當前節(jié)點的值加入答案數(shù)組；如果count > maxCount則將答案數(shù)組清空，再將當前節(jié)點的值加入答案數(shù)組。

完整的題解代碼如下

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）

• 初見題目的想法：這道題目要自底向上找最近公共祖先，而遍歷二叉樹一般只能自頂向下遍歷，即從根節(jié)點從上往下遍歷。那應該怎樣找到最近的公共祖先呢？
• 雖然無法從下往上訪問二叉樹的節(jié)點，但是可以從下往上處理二叉樹的節(jié)點，這對應的是后序遍歷。
• 通過后序遍歷，可以從下往上返回結(jié)果。所以當需要自底向上處理二叉樹的節(jié)點時，優(yōu)先考慮后序遍歷。
• 既然用后序遍歷，遞歸實現(xiàn)是比較容易實現(xiàn)的：
  • 傳入的參數(shù)和返回值：傳入當前子樹的根節(jié)點，節(jié)點p和節(jié)點q；返回值應該能標識是否找到節(jié)點p或者q。
  • 遞歸的終止條件：當前子樹的根節(jié)點為p或者q，則返回當前子樹的根節(jié)點；若當前子樹的根節(jié)點為空，說明這條路徑上沒有找到p或者q，返回nullptr
  • 單層遞歸的處理邏輯：采用后序遍歷，所以先去左子樹尋找p或者q，再去右子樹尋找p或者q；如果在左子樹和右子樹中分別找到了p和q，說明當前節(jié)點是p和q的公共祖先，則返回當前子樹的根節(jié)點；如果只在左子樹中找到了p或q的其中一個，則返回左子樹的根節(jié)點，右子樹同理。
• 由于是自底向上返回查找p和q的結(jié)果，所以找到的第一個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);
    }
};