9.13 DFSBFS 简单 101 Symmetric Tree 104 Maximum Depth of Binary Tree

101 Symmetric Tree

class Solution {
public:// 比较两个向量是否镜像对称bool isIdentical(const std::vector<int>& n1, const std::vector<int>& n2) {int n = n1.size();for (int i = 0; i < n; i++) {if (n1[i] != n2[n - i - 1]) return false;  // 镜像对应的元素比较}return true;}bool isSymmetric(TreeNode* root) {if (!root) return true;//出现的问题：左右子树的入队顺序、对负值和nullptr的区分// 使用queue来进行层次遍历queue<TreeNode*> prev;prev.push(root);while (!prev.empty()) {std::vector<int> curr;int size = prev.size();// 遍历当前层的所有节点for (int i = 0; i < size; i++) {TreeNode* node = prev.front();prev.pop();if (node) {curr.push_back(node->val);   // 当前节点值prev.push(node->left);       // 左子节点入队prev.push(node->right);      // 右子节点入队} else {curr.push_back(INT_MIN);     // 用INT_MIN来表示null节点}}// 检查当前层是否镜像对称if (!isIdentical(curr, curr)) {return false;}}return true;}
};

104 Maximum Depth of Binary Tree

class Solution {
public:int DFS(TreeNode* node, int height) {// 如果当前节点为空，返回当前高度if (!node) return height;// 如果是叶子节点，返回当前高度+1if (!node->left && !node->right) {return height + 1;}// 递归计算左右子树的最大高度，返回其中的较大值int leftHeight = DFS(node->left, height + 1);int rightHeight = DFS(node->right, height + 1);// 返回左右子树的最大高度return max(leftHeight, rightHeight);}int maxDepth(TreeNode* root) {// 深度搜索DFS，从高度0开始return DFS(root, 0);}
};