【二叉树】力扣OJ题

文章目录

前言
1. 翻转二叉树
- 1.1 题目
- 1.2 解题思路
- 1.3 代码实现
- 1.4 时空复杂度
2. 对称二叉树
- 2.1 题目
- 2.2 解题思路
- 2.3 代码实现
- 2.4 时空复杂度
3. 平衡二叉树
- 3.1 题目
- 3.2 解题思路
- 3.3 代码实现
- 3.4 时空复杂度
结语

前言

本篇博客主要介绍二叉树的经典 OJ 题，题目主要来源于力扣和牛客网，熟练掌握这些题型将会使你对二叉树的理解更上一层楼

1. 翻转二叉树

原题地址：力扣 226.翻转二叉树

1.1 题目

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

在这里插入图片描述

1.2 解题思路

看到是二叉树，我们就要考虑能不能使用递归法（大部分情况下是可以的）。在本题中，题目要求我们翻转二叉树，意思也就是以根节点为基准，交换左右子树（示例2），而且子树也同理（示例1），我们需要递归的交换左右子树，达到翻转二叉树的效果，最后返回根节点

根据思路我们可以总结出递归的两个条件：

终止条件

当前节点为 null 就返回
单层递归的逻辑

交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点

1.3 代码实现

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //终止条件
        if(root == null) {
            return null;
        }
        //暂时存储左节点，让左右节点交换
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        //交换结束，递归左节点
        invertTree(root.left);
        //递归右节点
        invertTree(root.right);
        //最后返回根节点
        return root;
    }
}

1.4 时空复杂度

时间复杂度为 O(N)，每个节点都会遍历到

空间复杂度为 O(N)，最坏情况下树形成链状

2. 对称二叉树

原题链接：力扣 101.对称二叉树

2.1 题目

给你一个二叉树的根节点 root ，检查它是否轴对称

在这里插入图片描述

2.2 解题思路

题目要求我们判断一棵二叉树是否轴对称，通过示例我们可以看出，轴对称是以根节点为基准的，也就是说，子树我们就不要求轴对称（要跟前一道题做区分）。就像示例 1，我们需要比较的是左子树的右子树跟右子树的左子树是否相等

在这里我们还是使用递归法：

终止条件

首先要判断两个节点是否为空：
- 左节点为空，右节点也为空，返回 true
- 左节点为空，右节点不为空，返回 false
- 左节点不为空，右节点为空，返回 false
此时排除了节点为空的情况，可以来判断节点里的值是否相等了：
- 相等返回 true，不相等返回 false
单层递归的逻辑

此时就要来往下递归，传入左节点的右孩子跟右节点的左孩子，再 与（&&） 上传入左节点的左孩子和右节点的右孩子，如果左右堆成就返回 true，有一侧不对称就返回 false

2.3 代码实现

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //先把根节点为null的情况排除掉
        if(root == null) {
            return true;
        }
        //传入根节点的左右子树
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        //都为null，则返回true
        if(leftTree == null && rightTree == null) {
            return true;
        }
        //因为上面排除了都为null的情况，所以这里只要有一个是null，就返回false
        if(leftTree == null || rightTree == null) {
            return false;
        }
        //都不为null，开始判断里面的值
        if(leftTree.val != rightTree.val) {
            return false;
        }
        //开始递归传入左子树的右节点和右子树的左节点
        //以及左子树的左节点和右子树的右节点，同为true就返回true，否则就只能返回false
        return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);
    }
}

2.4 时空复杂度

时间复杂度为 O(N)，每次递归都可以判断一对节点是否堆成，因此最多调用 N / 2 次

空间复杂度最差情况下也是 O(N)

3. 平衡二叉树

原题链接：力扣 110.平衡二叉树

3.1 题目

给定一个二叉树，判断它是否是平衡二叉树

平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1

在这里插入图片描述

3.2 解题思路

在力扣的题目中，默认根节点的深度是 1。要求该树所有节点的左右子树深度相差不超过 1，也就是小于等于 1，那我们就得去遍历，至于是哪种遍历，我们要根据题目需求，它让我们求高度还是求深度

求高度使用后序遍历：因为后序遍历是左右根（LRN），因此父节点可以根据左右节点返回上来的高度数再加一，层层向上，得到树的高度

求深度使用前序遍历：因为前序遍历是根左右（NLR），它能一直向下遍历，而不是向上去返回结果，求得深度

在本题中，我们要求的是深度，做后序遍历可以从底至顶返回子树深度，当前树的深度等于左子树的深度与右子树的深度中的最大值 +1。还是经典的递归：

终止条件

遇到空节点就终止，返回 0，表示此时以该节点为根节点的树的高度为 0
单层递归的逻辑

我们要比较左子树高度和其右子树高度的差值。分别求出其左右子树的高度，然后如果差值小于等于1，则返回 true，否则返回 false，表示已经不是二叉平衡树

3.3 代码实现

class Solution {
    public boolean isBalanced(TreeNode root) {
        //先判断根节点是否为null的情况
        if (root == null) {
            //是就返回true
            return true;
        }
        //求左子树的深度
        int leftH = getHeight(root.left);
        //求右子树的深度
        int rightH = getHeight(root.right);
        //相减的绝对值小于1，则表示以该节点为根节点的树平衡，返回true，再与上该节点的左子树和右子树
        return Math.abs(leftH - rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    //求树的深度
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //往下一直递归
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        //返回左右子树的深度的最大值，还要加一
        return leftHeight > rightHeight ?
                leftHeight+1 : rightHeight+1;
    }
}