立志重刷代码随想录60天冲冲冲!!——第十四天
226.翻转二叉树
前、后序遍历。就增加了交换位置
交换每个孩子节点的位置
class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return root; // 前序、后序可以。中序的话:左中左或右中右 swap(root->left, root->right); invertTree(root->left); invertTree(root->right); return root; } };
101. 对称二叉树
外侧对比,内侧对比
class Solution { public: // 收集孩子的信息,向上一级返回,需要后序(左右中) bool compare(TreeNode* left, TreeNode* right) { if (left == nullptr && right != nullptr) return false; else if (left != nullptr && right == nullptr) return false; else if (left == nullptr && right == nullptr) return true; else if (left->val != right->val) return false; bool outside = compare(left->left, right->right); bool inside = compare(left->right, right->left); return outside && inside; } bool isSymmetric(TreeNode* root) { bool res = compare(root->left, root->right); return res; } };
104.二叉树的最大深度
后序(左右中)计算最大高度。
1、确定返回值和参数(int和node)
2、终止条件
3、后序排列,逻辑是左右孩子最大值再➕1
class Solution { public: int GetMaxHeight(TreeNode* node) { if (node == nullptr) return 0; int LeftHeight = GetMaxHeight(node->left); int RightHeight = GetMaxHeight(node->right); int Height = max(LeftHeight, RightHeight) + 1; return Height; } int maxDepth(TreeNode* root) { int height = GetMaxHeight(root); return height; } };
111.二叉树的最小深度
处理逻辑非常重要!!
后序遍历(左右中)
左空右有,右➕1
左有右空,左➕1
左右都有,最小值➕1
class Solution { public: int GetMinHeight(TreeNode* node) { if (node == nullptr) return 0; int leftheight = GetMinHeight(node->left); int rightheight = GetMinHeight(node->right); // 需要注意的地方!!!此处逻辑非常重要 if (node->left == nullptr && node->right != nullptr) { return rightheight + 1; } else if (node->left != nullptr && node->right == nullptr) { return leftheight + 1; } else { int height = min(leftheight, rightheight) + 1; return height; } } int minDepth(TreeNode* root) { int height = GetMinHeight(root); return height; } };
代码随想录更新 文章被收录于专栏
冲冲冲冲冲冲!