刷题二叉树

二叉树的核心思想 - 递归 - 将问题分解为子问题

题型

递归遍历
迭代遍历
层序遍历 bfs：队列
各种递归题目：将问题分解为子问题
二叉搜索树 - 中序遍历是递增序列 TreeNode* &prev 指针
树形dp

面试经典 150 题 - 二叉树

104. 二叉树的最大深度

广度优先遍历

class Solution {
public:
    // 广度优先遍历
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int result = 0;
        while (!que.empty()) {
            ++result;
            int num = que.size();
            while (num--) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return result;
    }
};

递归

最大深度 = 1 + max(左子树最大深度，右子树最大深度)

class Solution {
public:
    // 递归：最大深度 = 1 + max(左子树最大深度， 右子树最大深度)
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

100. 相同的树

递归

树相同 --> 根节点相同 + 左子树相同 + 右子树相同

class Solution {
public:
    // 递归
    // 树相同 --> 根节点相同 + 左子树相同 + 右子树相同
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        } else if (p == nullptr || q == nullptr) {
            return false;
        }
        if (p->val != q->val) {
            return false;
        }
        if (isSameTree(p->left, q->left) == false) {
            return false;
        }
        if (isSameTree(p->right, q->right) == false) {
            return false;
        }
        return true;
    }
};

226. 翻转二叉树

递归

class Solution {
public:
    // 翻转二叉树 --> 
    // 根节点的左子树 = 将右子树进行反转
    // 根节点的右子树 = 将左子树进行反转
    TreeNode *invertTree(TreeNode *root) {
        if (root == nullptr) return nullptr;
        auto left = invertTree(root->left); // 翻转左子树
        auto right = invertTree(root->right); // 翻转右子树
        root->left = right; // 交换左右儿子
        root->right = left;
        return root;
    }
};

⭐️⭐️112. 路径总和

回溯

class Solution {
public:
    // 回溯
    bool backtracking(TreeNode* root, int path_sum, int targetSum) { 
        if (root == nullptr) return false;
        if (root->right == nullptr && root->left == nullptr) {  // 到达叶子节点，终止回溯
            return (path_sum + root->val == targetSum);
        }
        return (backtracking(root->left, path_sum + root->val, targetSum) || \
                backtracking(root->right, path_sum + root->val, targetSum));
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        return backtracking(root, 0, targetSum);
    }
};

⭐️⭐️迭代

class Solution {
public:
    // 递归: 树 存在和为 targetSum
    // 也即左子树存在和为 targetSum - root->val 或者 右子树存在和为 targetSum - root->val
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        if (root->left == nullptr && root->right == nullptr) {
            return (targetSum == root->val); 
        } 
        return (hasPathSum(root->left, targetSum - root->val) || \
                hasPathSum(root->right, targetSum - root->val));
    }
};

层序遍历

比较简单，不做讨论

面试经典 150 题 - 二叉树层次遍历

199. 二叉树的右视图

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (root == nullptr) return vector<int>{};
        queue<TreeNode*> que;
        que.push(root);
        vector<int> result;
        while (!que.empty()) {
            size_t n = que.size();
            for (size_t i = 0; i < n; ++i) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                if (i ==  n - 1) result.push_back(cur->val);
            }
        }
        return result;
    }
};

637. 二叉树的层平均值

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if (root == nullptr) return vector<double>{};
        queue<TreeNode*> que;
        que.push(root);
        vector<double> result;
        while (!que.empty()) {
            size_t n = que.size();
            double sum = 0.0;
            for (size_t i = 0; i < n; ++i) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                sum += cur->val;
            }
            result.push_back(sum / n);
        }
        return result;
    }
};

[102. 二叉树的层序遍历

](https://leetcode.cn/problems/binary-tree-level-order-traversal/?envType=study-plan-v2&envId=top-interview-150)

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) return vector<vector<int>>{};
        queue<TreeNode*> que;
        que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            size_t n = que.size();
            vector<int> layer(n, 0);
            for (size_t i = 0; i < n; ++i) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                layer[i] = cur->val;
            }
            result.push_back(layer);
        }
        return result;
    }
};

103. 二叉树的锯齿形层序遍历 - 写入的时候改一下索引即可

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (root == nullptr) return vector<vector<int>>{};
        queue<TreeNode*> que;
        que.push(root);
        vector<vector<int>> result;
        bool to_right = false;
        while (!que.empty()) {
            to_right = !to_right;
            size_t n = que.size();
            vector<int> layer(n, 0);
            for (size_t i = 0; i < n; ++i) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                if (to_right) {
                    layer[i] = cur->val;
                } else {
                    layer[n - 1 - i] = cur->val;
                }
            }
            result.push_back(layer);
        }
        return result;
    }
};

面试经典 150 题 - 二叉搜索树 - ⭐️`TreeNode*& prev`⭐️ - 中序遍历有序

98. 验证二叉搜索树

class Solution {
public:
    bool traversal(TreeNode* root, TreeNode*& prev) {
        if (root == nullptr) return true;
        if (!traversal(root->left, prev)) return false;
        if (prev != nullptr && prev->val >= root->val) return false;
        prev = root;
        return traversal(root->right, prev);
    }

    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return traversal(root, prev);
    }
};

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

使用数组暂存

class Solution {
public:
    // 二叉搜索树的特征：左子树 < 根节点 < 右子树
    // 中序遍历即可获得最小差值
    void traversal(TreeNode* root, vector<int>& vals, int& min_diff) {
        if (root == nullptr) return;
        traversal(root->left, vals, min_diff);
        if (!vals.empty()) min_diff = min(min_diff, root->val - vals.back()); 
        vals.push_back(root->val);
        traversal(root->right, vals, min_diff);
    }
    int getMinimumDifference(TreeNode* root) {
        vector<int> vals;
        int min_diff = INT_MAX;
        traversal(root, vals, min_diff);
        return min_diff;
    }
};

⭐️优化 - 使用一个 prev_val 即可

class Solution {
public:
    // 二叉搜索树的特征：左子树 < 根节点 < 右子树
    // 中序遍历即可获得最小差值
    // 如果不想使用数组暂存的话就需要存储一个 prev 指针
    void traversal(TreeNode* root, TreeNode*& prev, int& min_diff) {
        if (root == nullptr) return;
        traversal(root->left, prev, min_diff);
        if (prev != nullptr) min_diff = min(min_diff, root->val - prev->val); 
        prev = root;
        traversal(root->right, prev, min_diff);
    }
    int getMinimumDifference(TreeNode* root) {
        int min_diff = INT_MAX;
        TreeNode* prev = nullptr;
        traversal(root, prev, min_diff);
        return min_diff;
    }
};

230. 二叉搜索树中第 K 小的元素 - 想象用数组存储元素 - 实际只使用索引即可 - 注意终止条件

class Solution {
public:
    void traversal(TreeNode* root, int& val, int& count, int k) {
        if (root == nullptr || count >= k) return;  // 递归终止条件
        traversal(root->left, val, count, k);
        ++count;    // 如果用数组存储元素，想象这里是数组的第 count 个数字（从0开始）
        if (count == k) {
            val = root->val;
            return;
        }
        traversal(root->right, val, count, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        int val, count = 0;
        traversal(root, val, count, k);
        return val;
    }
};