《代码随想录》刷题打卡day12：二叉树part02

文章目录【226.翻转二叉树】【对称二叉树】【二叉树的最大深度】【二叉树的最小深度】【226.翻转二叉树】思路swap函数可以直接交换节点的左右孩子因为都是指针。思路和各种遍历节点方法相同都再复习一遍。【对称二叉树】递归法确定递归函数的参数和返回值因为我们要比较的是根节点的两个子树是否是相互翻转的进而判断这个树是不是对称树所以要比较的是两个树参数自然也是左子树节点和右子树节点。bool compare(TreeNode* left, TreeNode* right)确定终止条件要比较两个节点数值相不相同首先要把两个节点为空的情况弄清楚否则后面比较数值的时候就会操作空指针了。节点为空的情况有注意我们比较的其实不是左孩子和右孩子所以如下我称之为左节点右节点左节点为空右节点不为空不对称return false左不为空右为空不对称 return false左右都为空对称返回true此时已经排除掉了节点为空的情况那么剩下的就是左右节点不为空左右都不为空比较节点数值不相同就return false此时左右节点不为空且数值也不相同的情况我们也处理了。if (left NULL right ! NULL) return false; else if (left ! NULL right NULL) return false; else if (left NULL right NULL) return true; else if (left-val ! right-val) return false; // 注意这里我没有使用else确定单层递归的逻辑此时才进入单层递归的逻辑单层递归的逻辑就是处理 左右节点都不为空且数值相同的情况。比较二叉树外侧是否对称传入的是左节点的左孩子右节点的右孩子。比较内侧是否对称传入左节点的右孩子右节点的左孩子。如果左右都对称就返回true 有一侧不对称就返回false 。bool outside compare(left-left, right-right); // 左子树左、 右子树右 bool inside compare(left-right, right-left); // 左子树右、 右子树左 bool isSame outside inside; // 左子树中、 右子树中逻辑处理 return isSame;迭代法在迭代法中我们使用了队列需要注意的是这不是层序遍历而且仅仅通过一个容器来成对的存放我们要比较的元素知道这一本质之后就发现用队列用栈甚至用数组都是可以的。bool isSymmetric(TreeNode* root) { if (root NULL) return true; queueTreeNode* que; que.push(root-left); // 将左子树头结点加入队列 que.push(root-right); // 将右子树头结点加入队列 while (!que.empty()) { // 接下来就要判断这两个树是否相互翻转 TreeNode* leftNode que.front(); que.pop(); TreeNode* rightNode que.front(); que.pop(); if (!leftNode !rightNode) { // 左节点为空、右节点为空此时说明是对称的 continue; } // 左右一个节点不为空或者都不为空但数值不相同返回false if ((!leftNode || !rightNode || (leftNode-val ! rightNode-val))) { return false; } que.push(leftNode-left); // 加入左节点左孩子 que.push(rightNode-right); // 加入右节点右孩子 que.push(leftNode-right); // 加入左节点右孩子 que.push(rightNode-left); // 加入右节点左孩子 } return true; }【二叉树的最大深度】本题可以使用前序中左右也可以使用后序遍历左右中使用前序求的就是深度使用后序求的是高度。二叉树节点的深度指从根节点到该节点的最长简单路径边的条数或者节点数取决于深度从0开始还是从1开始二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数或者节点数取决于高度从0开始还是从1开始而根节点的高度就是二叉树的最大深度所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。递归法int getdepth(TreeNode* node) { if (node NULL) return 0; int leftdepth getdepth(node-left); // 左 int rightdepth getdepth(node-right); // 右 int depth 1 max(leftdepth, rightdepth); // 中 return depth; } int maxDepth(TreeNode* root) { return getdepth(root); }前序遍历真正求深度的逻辑classSolution{public:intresult;voidgetDepth(TreeNode*node,intdepth){resultdepthresult?depth:result;// 中if(node-leftNULLnode-rightNULL)return;if(node-left){// 左depth;// 深度1getDepth(node-left,depth);depth--;// 回溯深度-1}if(node-right){// 右depth;// 深度1getDepth(node-right,depth);depth--;// 回溯深度-1}return;}intmaxDepth(TreeNode*root){result0;if(rootNULL)returnresult;getDepth(root,1);returnresult;}};迭代法层序遍历的模板题int maxDepth(TreeNode* root) { if (root NULL) return 0; int depth 0; queueTreeNode* que; que.push(root); while(!que.empty()) { int size que.size(); depth; // 记录深度 for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); if (node-left) que.push(node-left); if (node-right) que.push(node-right); } } return depth; }【二叉树的最小深度】递归法如果左子树为空右子树不为空说明最小深度是 1 右子树的深度。反之右子树为空左子树不为空最小深度是 1 左子树的深度。 最后如果左右子树都不为空返回左右子树深度最小值 1 。int getDepth(TreeNode* node) { if (node NULL) return 0; int leftDepth getDepth(node-left); // 左 int rightDepth getDepth(node-right); // 右 // 中 // 当一个左子树为空右不为空这时并不是最低点 if (node-left NULL node-right ! NULL) { return 1 rightDepth; } // 当一个右子树为空左不为空这时并不是最低点 if (node-left ! NULL node-right NULL) { return 1 leftDepth; } int result 1 min(leftDepth, rightDepth); return result; } int minDepth(TreeNode* root) { return getDepth(root); }迭代法层序遍历➕出口调整int minDepth(TreeNode* root) { if (root NULL) return 0; int depth 0; queueTreeNode* que; que.push(root); while(!que.empty()) { int size que.size(); depth; // 记录最小深度 for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); if (node-left) que.push(node-left); if (node-right) que.push(node-right); if (!node-left !node-right) { // 当左右孩子都为空的时候说明是最低点的一层了退出 return depth; } } } return depth; }