刷题 二叉树

面试经典 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;
    }
};