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