226.翻转二叉树

leetcode链接

思路：
递归三部曲：

1. 确定递归函数的参数和返回值
2. 确定终止条件
3. 确定单层递归的逻辑

递归法

TreeNode* invertTreeNode(TreeNode* root)
{if(root==nullptr) return root;swap(root->left,root->right);invertTreeNode(root->left);invertTreeNode(root->right);return root;
}

迭代法（深度优先遍历）

 TreeNode* invertTree(TreeNode* root) {//迭代法 深度优先遍历stack<TreeNode*> st;//判断根节点是否为nullif(root==nullptr) return root;//根节点入栈st.push(root);//循环终止条件 栈为空while(!st.empty()){//中TreeNode* node = st.top();//出栈st.pop();//左节点入栈if(node->right) st.push(node->right); //左 if(node->left) st.push(node->left);    //右swap(node->left, node->right);          //交换}return root;}

层序遍历（广度优先遍历）

class Solution {
public:TreeNode* invertTree(TreeNode* root) {//广度优先遍历//创建队列queue<TreeNode*> que;if(root!=nullptr) //入队que.push(root);//循环终止条件 que为空while(!que.empty()){//size 保存队列中元素个数，需要弹出的元素个数int size = que.size();//遍历for(int i = 0;i<size;i++){TreeNode* node = que.front();//取出对头元素, node指向对头元素//出队que.pop();//交换节点swap(node->left,node->right);if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}//循环结束 返回rootreturn root;}
};

101. 对称二叉树

leetcode链接

递归法

递归三部曲：

1. 确定递归函数的返回值和参数
   参数自然也是左子树节点和右子树节点，返回值为bool类型

```c++
bool compareTree(TreeNode* left, TreeNode* right){
}
```

2. 确定递归函数的终止条件
   节点为空的情况有：

• 左节点为空，右节点不为空，不对称，return false
• 左不为空，右为空，不对称 return false
• 左右都为空，对称，返回true
  此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
• 左节点数值！=右节点数值，返回false
  左右都不为空，比较节点数值，不相同就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

3. 确定单层函数递归逻辑
   左右节点都不为空，且数值相同的情况

• 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
• 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
• 如果左右都对称就返回true ，有一侧不对称就返回false 。

bool outside = compareTree(left->left, right->right);
bool inside = compareTree(left->right, right->left);
bool isSame = outside && inside; 
return isSame ;

完整代码

class Solution {
public:bool compareTree(TreeNode* left, TreeNode* right){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//都不为空，数值相同的情况bool outside  = compareTree(left->left, right->right);bool inside = compareTree(left->right, right->left);bool isSame = outside&&inside;return isSame;}bool isSymmetric(TreeNode* root) {if(root==nullptr) return true;bool result = compareTree(root->left, root->right);return result;}
};

104.二叉树的最大深度

class Solution {
public:// 从根节点遍历，遍历左子树，遍历右子树//1. 确定递归函数参数和返回值int getLength(TreeNode* node){if(node==nullptr) return 0;int leftdepth = getLength(node->left);int rightdepth = getLength(node->right);int depth = 1 + max(leftdepth, rightdepth);return depth;}int maxDepth(TreeNode* root) {int result = getLength(root);return result;}
};

二叉树最小深度

class Solution {
public: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);}
};