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

226.翻转二叉树

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com，这里刷题顺序，详细题解，应有尽有！, 视频播放量 99009、弹幕量 572、点赞数 1519、投硬币枚数 891、收藏人数 698、转发人数 94, 视频作者代码随想录, 作者简介哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：二叉树的高度和深度有啥区别？究竟用什么遍历顺序？很多录友搞不懂 | LeetCode：104.二叉树的最大深度，怎么找二叉树的左下角？递归中又带回溯了，怎么办？| LeetCode：513.找二叉树左下角的值，不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索，一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树，贪心算法理论基础！，递归中带着回溯，你感受到了没？| LeetCode：257. 二叉树的所有路径，写出二叉树的非递归遍历很难么？这次再带你写出中序遍历的迭代法！|二叉树的非递归遍历 | 二叉树的遍历迭代法，构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树，看起来好像做过，一写就错！ | LeetCode：111.二叉树的最小深度，带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！https://www.bilibili.com/video/BV1sP4y1f7q7

思路：前序遍历，交换遍历到的节点左右节点的地址。注意如果用中序遍历，则是先翻转遍历到的节点的左子树，再翻转遍历到的节点的左右节点地址，此时原来的左子树经交换地址已经变为右子树，所以不能再翻转右子树，而是再翻转左子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //前序
    public TreeNode invertTree(TreeNode root) {
        invert(root);
        return root;
    }
    public void invert(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invert(root.left);
        invert(root.right);

    }
}

101. 对称二叉树

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：新学期要从学习二叉树开始！ | LeetCode：101. 对称二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com，这里刷题顺序，详细题解，应有尽有！, 视频播放量 60563、弹幕量 669、点赞数 1585、投硬币枚数 1386、收藏人数 256、转发人数 62, 视频作者代码随想录, 作者简介哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：当你过度准备了一场代码面试时……，一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵），我更完了，你看完了吗？，手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找，不喜欢写代码怎么办？？？还有救么？，Leetcode力扣 1-300题视频讲解合集｜手画图解版+代码【持续更新ing】，讲透二叉树的层序遍历 | 广度优先搜索 | LeetCode：102.二叉树的层序遍历，帮你把KMP算法学个通透！（理论篇），二叉树的高度和深度有啥区别？究竟用什么遍历顺序？很多录友搞不懂 | LeetCode：104.二叉树的最大深度，关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序https://www.bilibili.com/video/BV1ue4y1Y7Mf

思路：利用后序先看左右子树是否翻转一样，左节点的右子树翻转过去变成右节点的左子树，所以在递归过程中，左节点的右子树与右节点的左子树比较，同理左节点的左子树与右节点的右子树比较。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
         if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }
    public boolean isSymmetric(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;
        }
        //左右节点值一样，递归看左节点的左子树和右节点的右子树翻转是否一样
        boolean symmetric1 = isSymmetric(left.left, right.right);
        //同理
        boolean symmetric2 = isSymmetric(left.right, right.left);

        return symmetric1 && symmetric2;
    }
}

104.二叉树的最大深度

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：二叉树的高度和深度有啥区别？究竟用什么遍历顺序？很多录友搞不懂 | LeetCode：104.二叉树的最大深度_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com，这里刷题顺序，详细题解，应有尽有！, 视频播放量 65057、弹幕量 586、点赞数 1498、投硬币枚数 1136、收藏人数 344、转发人数 84, 视频作者代码随想录, 作者简介哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：平衡二叉树(AVL树)，一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵），【数据结构】递归求二叉树的高度，递归求二叉树深度算法过程，数据结构算法训练--06求二叉树的高度（方法二），【纯干货】三分钟教会你遍历二叉树！学不会举报我！！，4.02.节点&子树&边&度&高度，平衡二叉树两个考点。一告诉节点数求树的最大高度二时间复杂度，计算二叉树深度，计算机二级选择题树与二叉树https://www.bilibili.com/video/BV1Gd4y1V75u

思路：深度为节点到头节点的距离，高度为节点到叶子节点的距离。求深度一般用前序，求高度一般用后序。而最大深度又是最大高度，所以用后序求最大高度。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return getHight(root);
    }
    public int getHight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int lhight = getHight(node.left);
        int rhight = getHight(node.right);

        return Math.max(lhight, rhight) + 1;
    }
}

111.二叉树的最小深度

题目链接：. - 力扣（LeetCode）

文章链接：代码随想录

视频链接：看起来好像做过，一写就错！ | LeetCode：111.二叉树的最小深度_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com，这里刷题顺序，详细题解，应有尽有！, 视频播放量 45545、弹幕量 409、点赞数 970、投硬币枚数 728、收藏人数 152、转发人数 42, 视频作者代码随想录, 作者简介哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：贪心算法理论基础！，写出二叉树的非递归遍历很难么？这次再带你写出中序遍历的迭代法！|二叉树的非递归遍历 | 二叉树的遍历迭代法，带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！，怎么找二叉树的左下角？递归中又带回溯了，怎么办？| LeetCode：513.找二叉树左下角的值，我更完了，你看完了吗？，要理解普通二叉树和完全二叉树的区别！ | LeetCode：222.完全二叉树节点的数量，不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索，二叉搜索树中，需要掌握如何双指针遍历！| LeetCode：530.二叉搜索树的最小绝对差，普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树，你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树https://www.bilibili.com/video/BV1QD4y1B7e2

思路：方法一：用后序求跟节点到叶子节点的高度来求根节点到叶子节点的最短路径。

方法二：用层序遍历，利用了队列，如果队列弹出第一个左右子树均为空，那么这个就是叶子节点，则直接返回该节点所在层。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        return getHight(root);
    }

    public int getHight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int lhight = getHight(node.left);
        int rhight = getHight(node.right);
        if (node.left == null && node.right != null) {
            return rhight + 1;
        }
        if (node.left != null && node.right == null) {
            return lhight + 1;
        }

        return Math.min(lhight, rhight) + 1;
    }
}