226.翻转二叉树 （前序，后序）
题目链接 | 文档讲解 |视频讲解 : 链接
1.思路：
-
翻转的是指针，不是数值
-
前序遍历和后序遍历都可以
-
中序不行，中序遍历的顺序是左中右,反转左指针后,到根节点，在反转右节点(此时的右节点就是原先的左节点)，真正的右节点没有被处理
2.举例：
| 步骤 | 当前节点 | 操作 |
|---|---|---|
| 1 | 4 | 进入函数，调用 invertTree(2) |
| 2 | 2 | 调用 invertTree(1) |
| 3 | 1 | 左右为空，直接交换（没变化） |
| 4 | 2 | 回到 2，调用 invertTree(3) |
| 5 | 3 | 左右为空，交换（没变化） |
| 6 | 2 | 交换自己的左右子节点（2 的左右变成 3 和 1） |
| 7 | 4 | 回到 4，调用 invertTree(5) |
| 8 | 5 | 左右为空，交换（没变化） |
| 9 | 4 | 最后交换自己的左右子节点（4 的左右变成 5 和 2） |
2.代码：
public TreeNode invertTree(TreeNode root) {//递归终止条件if(root==null){return null;}//递归的逻辑//左invertTree(root.left);//右invertTree(root.right);//中 最后交换当前节点的左右子节点TreeNode temp=root.left;root.left=root.right;root.right=temp;return root;}101. 对称二叉树(后序)
题目链接 | 文档讲解 |视频讲解：链接
1.思路：
1.二叉树是否是对称二叉树,要比较的是左右子树是不是可以相互翻转,比较的是2棵树，所说递归遍历要同时遍历两颗树
2.判断的情况分为下面几种：
如果左子树为空,右子树不为空 返回false
如果右子树为空,左子树不为空 返回false
如果左子树为空,右子树为空 返回true
如果左子树不为空,右子树不为空,但是左右子树值不相等,返回false
3.如何比较元素是否相等
左子树的左节点和右子树的右节点进行比较
左子树的右节点和右子树的左节点进行比较
4.因为要遍历左右节点,遍历顺序是左右中,所以本题只能是后序遍历
2.代码：
public boolean isSymmetric(TreeNode root){return isSame(root.left,root.right);}public boolean isSame(TreeNode left,TreeNode right){//左节点为空 右节点不为空if(left==null && right!=null){return false;}//左节点不为空 右节点为空if(left!=null &&right==null){return false;}//左右节点均为空if(left==null &&left==null){return true;}//左右节点不为空 但值不相等if(left.val != right.val ){return false;}//比较外侧boolean leftResult = isSame(left.left, right.right);//比较内侧boolean rightResult = isSame(left.right, right.left);//中return leftResult && rightResult;}
104.二叉树的最大深度（前序,后序）
题目链接 | 文档讲解 |视频讲解：链接
二叉树的深度：前序遍历 根节点到该节点的最长简单路径边的条数或者节点数（从上到下 eg:井高度） 从1开始
二叉树的高度：后序遍历 指从该节点到叶子节点的最长简单路径边的条数或者节点数（从下到上 eg:楼高度）从1开始
1.思路：
二叉树的最大深度=二叉树的最大高度，所以可以采取后序遍历
递归计算的是当前节点左子树和右子树的高度，所以需要将当前节点加上，最后的值+
2.代码：
public int maxDepth(TreeNode root){//递归终止条件if(root==null){return 0;}//递归逻辑//左子树最大深度int leftHeight=maxDepth(root.left);//右子树最大深度int rightHeight=maxDepth(root.right);//返回左右子树最大深度+1（当前节点深度）return Math.max(leftHeight,rightHeight)+1;}111.二叉树的最小深度 （前序，后序）
题目链接 | 文档讲解 |视频讲解：链接
1.思路：
-
题目上求的是最小深度，指的是从根节点到最近叶子结点的距离
-
本题代码使用的是后序遍历（前序遍历也可以），其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离 也同样是最小深度
-
因为求的是最小，而且求的是根节点到叶子节点的最小深度，所以需要排除左子树或叶子树为空的情况
2.代码：
public int minDepth(TreeNode root){//递归终止条件if(root==null){return 0;}//递归逻辑 （后续遍历）int leftHeight =minDepth(root.left);int rightHeight =minDepth(root.right);//递归逻辑//左子树为空，右子树不为空if(root.left==null && root.right!=null){return rightHeight+1;}//右子树为空，左子树不为空if(root.left!=null && root.right==null){return leftHeight+1;}//左右子树都不为空int result=Math.min(leftHeight,rightHeight)+1;return result;}
