力扣算法刷题 Day 14
226. 翻转二叉树
题目链接
226. 翻转二叉树 - 力扣（LeetCode）
思路
递归法：交换左右子树即可，函数退出状态为当前节点为NULL。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root == NULL) return root; swap(root->left,root->right); invertTree(root->left); invertTree(root->right); return root; } };迭代法：之前写过迭代法遍历，自然也可以写出这个。注意用到栈的数据结构，左右子树入栈时先右边入栈。以及操作时避免空指针异常需要先做判断。
TreeNode* invertTree(TreeNode* root) { stack <TreeNode*> st; if(root == NULL) return root; st.push(root); while(!st.empty()) { TreeNode* tmp = st.top(); st.pop(); swap(tmp->left,tmp->right); if(tmp->right) st.push(tmp->right); if(tmp->left) st.push(tmp->left); } return root; }文章详解
226.翻转二叉树 | 代码随想录
101. 对称二叉树
题目链接
101. 对称二叉树 - 力扣（LeetCode）
思路
递归法：要判断是否反转，就要比较左边的外/内侧节点和右边的外/内侧节点是否相同。函数的返回值应该是bool类型，入口参数就是左右孩子节点。递归结束条件为，左右孩子存在空或都不空且数值不相等。进入递归逻辑，左树要 左右根，右树要右左根。
文章详解
101. 对称二叉树 | 代码随想录
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool compare(TreeNode *left,TreeNode * right) { if(left == NULL && right != NULL) return false; if(right == NULL && left != NULL) return false; if(left == NULL && right == NULL) return true; if(left->val != right->val) return false; bool out = compare(left->left,right->right); bool in = compare(left->right,right->left); return out&∈ }; bool isSymmetric(TreeNode* root) { if(root == NULL) return true; return compare(root->left,root->right); } };104. 二叉树的最大深度
题目链接
104. 二叉树的最大深度 - 力扣（LeetCode）
思路
递归法：函数返回值：int 入口参数：根节点root 结束条件：当前节点为空 递归：求左/右子树的深度，取最大值加1
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int getdepth(TreeNode * root) { if(root == NULL) return 0; int ld = getdepth(root->left); int rd = getdepth(root->right); int max1 = 1 + max(ld,rd); return max1; } int maxDepth(TreeNode* root) { int dep = getdepth(root); return dep; } };迭代法：按照层序遍历的思路，遍历多少层就是深度多少。注意数据结构的选择为队列。
int maxDepth(TreeNode* root) { queue <TreeNode *> que; if(root == NULL) return 0; que.push(root); int depth = 0; 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; }文章详解
104.二叉树的最大深度 | 代码随想录
111. 二叉树的最小深度
题目链接
111. 二叉树的最小深度 - 力扣（LeetCode）
思路
和最大深度的差异在于，最小深度的定义为： 叶子节点到根节点的最小距离。何为叶子节点？左右子节点均为空。因此，当有一个子节点为空而另一个不为空时，该节点不为最短节点。
文章详解
111.二叉树的最小深度 | 代码随想录
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int getdepth(TreeNode* root) { if(root == NULL) return 0; int ld = getdepth(root->left); int rd = getdepth(root->right); if(root->left == NULL && root->right != NULL) { return 1 + rd; } else if(root->right ==NULL&&root->left != NULL ) { return 1 + ld; } int minidep = min(ld,rd) + 1; return minidep; } int minDepth(TreeNode* root) { return getdepth(root); } };