代码随想录算法训练营第14天/优先掌握递归

226.反转二叉树

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

文档/视频链接：代码随想录 (programmercarl.com)

代码随想录想法

要翻转二叉树，只需把每个节点的左右孩子交换一下。

有两种遍历方式：递归遍历，层序遍历。都可以。

递归有三种方式：前序，中序，后序。

写递归：条件参数+终止条件+递归方式

其中中序是不可以的：左支树反转，左右孩子反转，本应反转右支树，但实际此时的右支树是反转过的左支树。相当于把左支树反转了两遍。

算法

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //终止条件
        if(root==null)return root;
        //采用中序遍历；
        swap(root);//交换当前节点的左右子树
        invertTree(root.left);//遍历左子树
        invertTree(root.right);//遍历右子树
        return root;
    }
    public void swap(TreeNode root){
        TreeNode tempNode = root.left;
        root.left = root.right;
        root.right=tempNode;
    }
    //bfs
    public TreeNode invertTreeByBfs(TreeNode root){
        if(root==null)return null;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()){
            int size = deque.size();
            while (size>0){
                //交换当前节点
                TreeNode curNode = deque.poll();
                swap(curNode);
                deque.offer(curNode.left);
                deque.offer(curNode.right);
                size--;
            }
        }
        return root;
    }
}

101.堆成二叉树

题目链接：101. 对称二叉树 - 力扣（LeetCode）

视频/文档链接：代码随想录 (programmercarl.com)

第一想法

层序遍历：size循环时，建立一个大小为（size+1）/2的栈,左边只会等于右边或者多一个。所以前size/2+1时将节点入栈，其余匹配值是否相等，相等时出栈。循环结束时检查此层的栈是否为空，若不为空则说明不对成。

代码随想录

判断二叉树是否对成是要比较根节点的左右子树是否可以相互反转，实际上比较的是两个树（根节点的左右子树），即在递归遍历过程中要同时遍历两棵树

比较逻辑：比较外侧元素是否相等，比较内侧元素是否相等，如果等相等则将信息返回上一层。从左子树或者右子树的视角看都是后序遍历。

如果上来就看网上各种简洁的代码，看起来真的很简单，但是很多逻辑都掩盖掉了，而题解可能也没有把掩盖掉的逻辑说清楚。

盲目的照着抄，结果就是：发现这是一道“简单题”，稀里糊涂的就过了，但是真正的每一步判断逻辑未必想到清楚。

递归的代码都很简单，但是尤其是逻辑都很难理解透彻，就容易当成简单题放过去了。 

关于层序法:选择双端队列就方便很多了。成对取出，而且特别可以学习终止条件这快逻辑判断的手法，写的非常简洁和巧妙。

代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirroredBetweenTwoTree(root.left,root.right);
    }
    public boolean isMirroredBetweenTwoTree(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{//左右相等进入单层循环
            Boolean outSide = isMirroredBetweenTwoTree(left.left,right.right);//外侧是否相等
            Boolean inSide = isMirroredBetweenTwoTree(left.right,right.left);//内侧是否相等
            return outSide&&inSide;
        }
    }
}
//迭代法
class Solution1{
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root.left);
        deque.offerLast(root.right);
        while (!deque.isEmpty()){
            TreeNode leftNode = deque.pollFirst();
            TreeNode rightNode = deque.pollLast();
            //以下的判断手法，孰能生巧。
            if(leftNode==null&&rightNode==null)
                continue;
            if(leftNode==null||rightNode==null||leftNode.val!=rightNode.val){
                return false;
            }
            deque.offerFirst(leftNode.left);
            deque.offerFirst(leftNode.right);
            deque.offerLast(rightNode.right);
            deque.offerLast(rightNode.left);
        }
        return true;
    }
}

104.二叉树的最大深度

题目链接：104. 二叉树的最大深度 - 力扣（LeetCode）

文档/视频链接：

代码随想录

当时写层序遍历，初始deep=0，进入while（！deque.isEmpty)后每遍历一层就deep++。最后返回deep即可。

二叉树的最大深度=根节点的高度 ，并且前序求深度，后序求高度。

看完前序和后序版本才知道为什么说前序求深度，后序求高度。

前序的话，你从根节点开始就知道这里深度是1，然后一层层推下去，你走到新一层就知道这一层深度是多少，这也是为什么函数返回类型是​编辑void。你只需要靠一个变量记录全局的最大/最小值就行了。

后序的话，你要一层层迭代，直到找到一个​编辑leaf节点才知道这里高度是1了，然后才能一层层回退，去算路上的每一层高度是多少，所以需要返回int类型的高度。因为不等到下面函数返回值，你都不知道这层高度是多少。

还有为什么在另一题，算二叉树最小深度的时候，用后序需要那么多策略，前序就很简单。因为拿到了下面返回来的情况，才能根据不同情况决定你这层高度是多少，但深度你不需要返回值就知道了，因为每进入一次递归深度必然+1

代码

class Solution {
    //求最大深度实际上等于求根节点的高度
    public int maxDepth(TreeNode root) {
        //终止条件
        if(root==null)return 0;
        //后序遍历，知道左右节点信息然后返回此节点
        int leftHeight = maxDepth(root.left);//左节点高度
        int rightHeight = maxDepth(root.right);//右节点高度
        return 1+Math.max(leftHeight,rightHeight);//最后处理当前节点。
    }
}

111.二叉树最小深度

题目链接：111. 二叉树的最小深度 - 力扣（LeetCode）

文档/视频链接：代码随想录 (programmercarl.com)

代码与求最大深度有相近之处。

题目要求：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点

如果直接返回 1+ min(leftHeight,rightHeight) ,那么没有左孩子的分支会算为最短深度，显然是不对的。

所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。

反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

代码 

class Solution {
    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 1+rightHeight;
        if(root.left!=null&&root.right==null){
            return  1+leftHeight;
        }
        return 1+Math.min(leftHeight,rightHeight);
    }
}