Java数据结构二叉树练习

1.检查两棵二叉树是否都是相同的练习

我要求时间复杂度为1，所以我们不用前序中序后序是否都一样来进行判断

如何判断二叉树是否都是相同的子问题方式

先判断根节点是否相同

再判断左子树和右子树是否都是相同的

先用代码判断不相同的情况，都相同的化那么就可以直接输出true了

图总结三种来判断二叉树是否是相同的

代码实现

第二种写法是最好的看你喜欢哪个

. - 力扣（LeetCode）练习网址

2.反转二叉树练习

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

其中这个问题的思路就是将第根节点的下面两个的第一个的叶子节点进行反转（简单思路）

图解

定义一个节点类型的tmp，用tmp的左右节点来进行节点的交换，然后遍历整个数组。

3.判断两个二叉树是否是平衡二叉树（AVL树我会在高阶数据结构中进行讲解）（难度高）

在做这个题之前把二叉树前面的内容复习一下包括练习、

. - 力扣（LeetCode）

图解

代码实现

先用我们之前写的方法来算出二叉树的高度，然后题目的要求是：每个子树和根（虚拟为跟更好的可以理解）的深度相减的绝对值要小于2，所以我们遍历整个二叉树，在if语句中要遍历两次一次是左边，一次是右边，这时候就可以将二叉树的所有节点进行判断是否是满足条件的。如果满足条件的话那么就输出true

代码逻辑图复杂度是n^2.

我们要定义的代码的复杂度要求是n，所以我们重新写一下这段代码

class Solution {
    public boolean isBalanced(BinaryTree.TreeNode root) {
        if (root == null) {
            return true;
        }
     return getHeight(root) >= 0;
    }

    private int getHeight(BinaryTree.TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if (Math.abs(leftHeight - rightHeight) <= 1 && leftHeight >= 0 && rightHeight >=0) {
            return Math.max(leftHeight,rightHeight) +1;//计算出高度
        }else{
            return -1;
        }
    }
}