数据结构（Java）：力扣&牛客 二叉树面试OJ题（一）

时间：2024-07-20 07:11:36

???? ​​​​​​目录 ????

1、题一：检查两棵树是否相同

 1.1 思路分析

1.2 代码

2、题二：另一棵树的子树

2.1 思路分析

 2.2 代码

3、题三：翻转二叉树

3.1 思路分析

3.2 代码

4、题四：判断树是否对称

4.1 思路分析

 4.2 代码

 5、题五：判断是否为平衡二叉树

5.1 思路分析

5.1.1 平衡二叉树概念

5.1.2 思路一  O(n^2)

5.1.3 思路一代码 

 5.1.4 思路二 ：改善为O(n)【字节跳动面试题】

 5.1.5 思路二代码

6、题六：将二叉搜索树转化为有序的双向链表

6.1 二叉搜索树的性质

6.2  思路分析

6.3 代码

7、题七：二叉树的遍历和构建

7.1  思路分析

​7.2 代码

1、题一：检查两棵树是否相同

. - 力扣（LeetCode）

 1.1 思路分析

两棵树相同，需要注意以下几点：

  1. 两棵树结构相同，若结构不相同，那两棵树必然是不相同的
  2. 在结构相同的前提下，还需满足节点值相同
  3. 若结构和节点值都相同，那么两棵树相同

额外注意的是：若两棵树为空，那么也是相同的。

 我们可以按照子问题遍历的思想，当左子树和右子树中全部节点同时满足以上条件，说明两棵树相等。

1.2 代码

时间复杂度：O（min（m,n））

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //如果两棵树都为空，那么两棵树相同
        if(p == null && q == null) {
            return true;
        }
        //如果两棵树的结构不同，那这两棵树必然不同
        if(p != null && q == null || p == null && q != null) {
            return false;
        }
        //走到这里，说明两棵树的结构相同且不为空，那判断他们的节点值即可
        //若节点值不相同，则说明两棵树不相同，返回false
        if(p.val != q.val) {
            return false;
        }
        //递归遍历
        //左右两棵子树必须同时满足条件 
        //才能说明两棵树才相同
        return isSameTree(p.left,q.left) &&
        isSameTree(p.right,q.right);
    }
}

2、题二：另一棵树的子树

. - 力扣（LeetCode）

2.1 思路分析

一棵树的子树 需要满足：

  1. 这棵子树包括主树的某个节点，和这个节点的所有后代节点
  2. 这棵树自身，也可看做自己的子树

了解子树概念后，我们可以按照以下思路解决问题：

  1. 判断子树根节点subRoot和主树根节点root是否相同
  2. 若相同，则调用检查两棵树是否相同的方法（题一），若相同，则为子树
  3. 若不相同，继续遍历，判断子树是否和root的左子树相同 
  4. 若不相同，继续遍历，判断子树是否和root的右子树相同
  5. 递归解决问题 

 2.2 代码

 时间复杂度：O(m*n)

 因为最坏的情况下：

 每个节点和子树值相同，但判断树是否相同时，总是最后一个节点不相同

 /**
 时间复杂度为：O(m*n)
 因为最坏的情况下：
 每个节点和子树值相同，但判断树是否相同时，总是最后一个节点不相同
*/
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //如果递归到空，说明没有找到子树，返回false
        if(root == null) {
            return false;
        }
        //判断当前节点的整颗树和子树是否相同即可
        if(isSameTree(root,subRoot)) {
            return true;
        }
        //如果递归遇见了子树 则一路返回true
        if(isSubtree(root.left,subRoot)) return true;
        if(isSubtree(root.right,subRoot)) return true;
        //本次递归没有找见子树 返回false
        return false;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1.先判断结构是否是一样的
        if (p != null && q == null || p == null && q != null) {
            return false;
        }
        // 上述if语句 如果没有执行，意味着两个引用 同时为空 或者同时不为空
        if (p == null && q == null) {
            return true;
        }
        // 都不为空 判断值是否一样
        if (p.val != q.val) {
            return false;
        }
        // 都不为空且值一样
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

3、题三：翻转二叉树

. - 力扣（LeetCode）

3.1 思路分析

 这道题的思路很简单，就是：将每个节点的左右子树进行交换。

我们可以以前序遍历思想遍历所有节点，在访问当前树的根节点时将其左右子树进行交换。

3.2 代码

根据解题思想，很清晰的分析出时间复杂度为：O（n）

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        //交换左右子树
        swapNode(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public void swapNode(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

4、题四：判断树是否对称

. - 力扣（LeetCode）

4.1 思路分析

要判断这颗树是对称的，

  • 就要判断，根节点的左子树和右子树是对称的 
  • 要判断根节点的左子树和右子树是对称的 ，需要左右子树的结构相同；在结构相同前提下，节点的值要相同
  • 如果结构相同了，值也相同了，那么要递归去判断：左子树的左树和右子树的右树是否轴对称（是否结构相同、值相同）；以及左子树的右树和右子树的左树是否轴对称（是否结构相同、值相同）。（均满足）
  • 我们只能递归来一个节点一个节点的去遍历，去判断，去比较

 

 4.2 代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        //空树对称
        if(leftTree == null && rightTree == null) {
            return true;
        }
        //结构不相同 必定不对称
        if(leftTree != null && rightTree == null || 
        leftTree == null && rightTree != null) {
            return false;
        }
        //节点值不相同 必定不对称
        if(leftTree.val != rightTree.val) {
            return false;
        }
        //左子树的左树和右子树的右树 
        //左子树的右树和右子树的左树
        //都要对称
        return isSymmetricChild(leftTree.left,rightTree.right) 
        && isSymmetricChild(leftTree.right,rightTree.left);
    }
}

 5、题五：判断是否为平衡二叉树

. - 力扣（LeetCode）

5.1 思路分析

5.1.1 平衡二叉树概念

如果一棵树是平衡二叉树，那么满足：

  • 树中所有节点的左右子树高度差<=1 
  • 也就是说，每一棵子树都是平衡二叉树

根据平衡二叉树的概念，我们有以下两种思路解决问题。

5.1.2 思路一  O(n^2)

  • 递归遍历所有节点，求出每个节点的左右子树高度差，若出现>=2的情况，立即返回false
  • 当前节点的左树上的节点和右树上的节点全部满足高度差<=1 时，说明为平衡二叉树
  • 该思路时间复杂度为O（n^2），求根节点高度的方法时间复杂度本来就为O（n），而要求得所有节点的高度，时间复杂度就为O（n^2）

5.1.3 思路一代码 

class Solution {
     public boolean isBalanced(TreeNode root) {
         //空树 平衡
         if(root == null) {
             return true;
         }
         //当前节点左子树高度
         int h1 = getHeight(root.left);
         //当前节点右子树高度
         int h2 = getHeight(root.right);
         int h = Math.abs(h1-h2);//高度差
         //不平衡
         if(h >= 2) return false;
         //左子树和右子树同时平衡 说明整棵树平衡
         return 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);

         //树的高度为 左子树高度和右子树高度的最大值+节点自身的1个高度
         return leftHeight > rightHeight
                 ? leftHeight + 1
                 : rightHeight + 1;
     }
}

 5.1.4 思路二 ：改善为O(n)【字节跳动面试题】

 思路一虽然能解决问题，但时间复杂度达到了O(n^2)，并且产生了很多次重复的计算,例如：圈中节点的高度，在计算它祖先的高度时就被计算了多次，产生了很多重复的计算。

如果要将时间复杂度改善为O(n)，该如何完成呢？

O(n)思路分析：

  • 我们可以只求根节点的高度
  • 在求节点高度时，我们使用递归遍历思想，返回的是左右子树高度的最大值+1（左右子树最大高度+节点自身1个高度）
  • 而我们可以将求高度的方法进行改善，在递归过程中，一旦发现左右子树高度差绝对值>=2时（说明不平衡），立即返回负数（标记，其他标记也可）；如果高度差绝对值<=1时（说明平衡），返回正常的高度值即可。如若发现返回的是负数，立即一路返回负数。
  • 最终判断方法的返回值即可，若为负数，则说明该树不平衡；若为正数（高度值），说明该树平衡。

 

 5.1.5 思路二代码

class Solution {
    /**
    时间复杂度：O（n）
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }

        //负数说明该树不平衡
        return getHeight(root) > 0;
    }


    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        //如若发现返回的是负数，则说明该树一定不平衡，一路返回负数
        if(leftHeight < 0) {
            return -1;
        }
        //如若发现返回的是负数，则说明该树一定不平衡，一路返回负数
        int rightHeight = getHeight(root.right);
        if(rightHeight < 0) {
            return -1;
        }

        //如果绝对值<=1 说明当前树平衡，返回高度值
        if(Math.abs(leftHeight - rightHeight) <= 1) {
            return Math.max(leftHeight , rightHeight) + 1;
        }else {
            //否则返回负数
            return -1;
        }
    }
}

6、题六：将二叉搜索树转化为有序的双向链表

二叉搜索树与双向链表_牛客题霸_牛客网

6.1 二叉搜索树的性质

二叉搜索树，又称二叉排序树、二叉查找树，具有以下性质：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 二叉搜索树可以为空树
  • 以中序遍历来遍历一棵二叉搜索树，那么得到的序列就是一个有序的升序序列。

6.2  思路分析

以中序遍历递归这棵二叉搜索树，将得到的根节点依次连接（修改其左右指针），得到的就是排好序的双向链表。

  • 借助中序遍历思想递归，遍历各个节点，修改指向
  • 将每个节点的left域当做双向链表中的prev域，将right域当做next域
  • 借助一个成员变量prev，存储上一个节点的地址，完成各节点指向的修改和连接

6.3 代码

时间复杂度：O（n）

public class Solution {
    //定义一个成员变量 存储上一个节点的地址
    TreeNode prev;//初始值为null

    public void ConvertNode(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return;
        //中序遍历思想递归
        ConvertNode(pRootOfTree.left);
        
        //修改前驱，将当前节点的left域更改为前一个节点的地址
        pRootOfTree.left = prev;
        if (prev != null) {
            //当prev不为空时，修改后继
            //将其right域修改为当前节点的地址（prev本就是当前节点的前驱）
            prev.right = pRootOfTree;
        }
        //更新prev
        prev = pRootOfTree;

        ConvertNode(pRootOfTree.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        ConvertNode(pRootOfTree);

        TreeNode head = pRootOfTree;
        //找头结点
        //转换成双向链表后，链表的头结点就在pRootOfTree的左边
        //头结点的left（前驱）为null
        while(head.left != null) {
            head = head.left;
        }

        return head;
    }
}

7、题七：二叉树的遍历和构建

二叉树遍历_牛客题霸_牛客网

7.1  思路分析

我们知道，如果仅仅根据一个遍历方式的结果是无法构建出一棵二叉树的，必须有两个遍历方式且必须包含中序遍历。

而这道题是不同的，因为题目给出的遍历结果包含了空树，所以仅仅利用一个遍历方式我们就可以构建出二叉树。

只要构建出这棵二叉树，我们再使用中序遍历递归打印节点值就可以了。

难点在，如何使用代码根据前序遍历来构建二叉树？

思路如下：

  • 题目仅仅给出了main方法，意味着我们要自己创建节点，创建的节点类要满足树中节点的要求，包含val域（char类型）、left域、right域，同时要给出构造方法
  • 创建二叉树，肯定是要遍历前序遍历结果的字符串（这里以静态i成员遍历字符串）
  • 给出的是前序遍历结果，所以要以前序遍历的思想递归来创建树
  • 如果遍历到的字符不是'#'，说明不是空树，实例出该值的节点，i++（此时仅仅实例节点，各节点间并没有连接）
  • 创建左子树，创建右子树
  • 如果遇到的字符是'#'，说明遇到是空树，i++，返回空节点（递归回退），上一个节点的left或者right接收
  • 如果节点的左子树或者右子树创建完成，递归回退，上一个节点的left或者right接收
  • 如果节点的左子树和右子树都创建完成（本次递归函数结束），递归回退，上一个节点的left或者right接收
  • 也就是说，我们在递归回退的过程中，完成节点之间的连接
  • 最后一步，以中序遍历形式来访问根节点并打印

注意：这里因为题目条件限制，只能使用静态成员i来遍历字符串。但是对于我们实际的应用，不建议使用静态成员，因为当创建多个对象时，他们都会使用并改变i的值，而创建二叉树时，必须从0下标处遍历字符串！！！

7.2 代码

import java.util.Scanner;

//节点
class TreeNode {
    TreeNode left;
    TreeNode right;
    char val;

    public TreeNode(char val) {
        this.val = val;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case

            //防止有多组测试用例，每次使用时i要置0
            Main.i = 0;
            String str = in.nextLine();
            TreeNode root = creatTree(str);
            InOrder(root);
        }

    }
    public static int i;
    public static TreeNode creatTree(String str) {
        TreeNode node = null;
        if (str.charAt(i) != '#') {
            //不是空树，就实例化该值的节点
            node = new TreeNode(str.charAt(i));
            i++;
            //在递归回退的过程中，完成节点之间的连接
            node.left = creatTree(str);
            node.right = creatTree(str);
        } else {
            //是空树，i++
            i++;
        }
        return node;
    }
    //中序遍历，打印根节点
    public static void InOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        InOrder(root.left);
        System.out.print(root.val + " ");
        InOrder(root.right);
    }
}

相关文章