代码随想录算法训练营Day-14 | 226.翻转二叉树、101. 对称二叉树、104.二叉树的最大深度、111.二叉树的最小深度

226.翻转二叉树思路只需要前序或后序遍历中序遍历会导致有地方反转两次遍历到一个节点就进行反转即可代码在前序遍历的递归函数基础上增加左右节点交换即可。class Solution { public: void inverdigui(TreeNode* root){ if(rootNULL) return; //-----交换---- TreeNode* tmp; tmp root-right; root-right root-left; root-left tmp; //------------- inverdigui(root-left); inverdigui(root-right); } TreeNode* invertTree(TreeNode* root) { inverdigui(root); return root; } };101. 对称二叉树思路递归终止条件是左右孩子空的情况或者值不一样都返回false都为空返回正确递归逻辑是外层子树进行比较内层子树进行比较class Solution { public: bool compare(TreeNode* left,TreeNode* right){ if(leftNULL rightNULL) return true; else if(leftNULL right!NULL) return false; else if(left!NULL rightNULL) return false; else if(left-val ! right-val) return false; bool outside compare(left-left,right-right);//外层树 bool inside compare(left-right,right-left);//里层树 return outsideinside; } bool isSymmetric(TreeNode* root) { if(root NULL) return true; else return compare(root-left,root-right); } };104.二叉树的最大深度思路最大深度是在后续遍历基础上把处理改为了两个子树深度取最大值再加一也可使用前序遍历终止条件是左右节点都是空就结束遍历定义结果变量递归函数只对变量进行操作但不返回值每次遍历先对变量执行若传入深度变量大于结果变量结果变量就取更大的值处理完之后进行左右递归分别传入当前节点的左右孩子节点以及当前传入深度值加一主函数中对result赋值0对初始depth赋值1。class Solution { public: int maxDepthdigui(TreeNode* cur){ if(curNULL) return 0; int left_depth maxDepthdigui(cur-left); int right_depth maxDepthdigui(cur-right); return max(left_depth,right_depth)1; } int maxDepth(TreeNode* root) { return maxDepthdigui(root); } };111.二叉树的最小深度思路只实现了后续遍历方法再最大深度的后续遍历法基础上在单层循环逻辑上增加了判断条件来避免左节点不存在但右节点存在导致当前节点被判断为高度为1的情况。增加的判断为左节点空右节点不空返回右节点高度1右节点空左节点不空返回左节点高度1class Solution { public: int getmindepth(TreeNode* node){ if(nodeNULL) return 0; int depth_left getmindepth(node-left); int depth_right getmindepth(node-right); if(node-left NULL node-right ! NULL) return 1depth_right; if(node-left ! NULL node-right NULL) return 1depth_left; int result min(depth_left,depth_right)1; return result; } int minDepth(TreeNode* root) { if(rootNULL) return 0; return getmindepth(root); } };