算法面试通关40讲 – 二叉树/递归

98. 验证二叉搜索树

递归

class Solution {
    TreeNode *leftMost;
    TreeNode *rightMost;
    bool limitYourself(TreeNode *root, int min, int max)
    {
        if (root == nullptr) {
            return true;
        }
        if (root->val <= min || root->val >= max) {
            if (!((root == leftMost && root->val == INT_MIN) || (root == rightMost && root->val == INT_MAX))) {
                return false;
            }
        }
        return limitYourself(root->right, root->val, max) && limitYourself(root->left, min, root->val);
    }

public:
    bool isValidBST(TreeNode *root)
    {
        leftMost = root;
        rightMost = root;
        while (leftMost->left != nullptr) {
            leftMost = leftMost->left;
        }
        while (rightMost->right != nullptr) {
            rightMost = rightMost->right;
        }
        return limitYourself(root, INT_MIN, INT_MAX);
    }
};

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

递归

class Solution {
    TreeNode* pp;
    TreeNode* qq;
public:
    //     [ r ]          [ p ]
    //     /  \           /
    // [ p ]   [ q ]   [ q ]
    TreeNode* giveMeHighestPQ(TreeNode* r) {
        if (r == nullptr || r == pp || r == qq) {
            return r;
        }
        auto ll = giveMeHighestPQ(r->left);
        auto rr = giveMeHighestPQ(r->right);
        if (ll != nullptr) {
            if (rr != nullptr) {
                return r;
            }
            return ll;
        }
        return rr;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        pp = p;
        qq = q;
        return giveMeHighestPQ(root);
    }
};

129. 求根节点到叶节点数字之和

class Solution {
    void down(TreeNode* middle, int& ans, int cur) {
        int tmp = cur * 10 + middle->val;
        if (middle->left == nullptr && middle->right == nullptr) {
            ans += tmp;
            return;
        }
        if (middle->left != nullptr) {
            down(middle->left, ans, tmp);
        }
        if (middle->right != nullptr) {
            down(middle->right, ans, tmp);
        }
    }
public:
    int sumNumbers(TreeNode* root) {
        int ans {};
        down(root, ans, 0);
        return ans;
    }
};