【数据结构（八）上】二叉树经典习题-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构（八）上】二叉树经典习题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

❣博主主页: 33的博客❣
▶文章专栏分类: Java从入门到精通◀
🚚我的代码仓库: 33的代码仓库🚚
🫵🫵🫵关注我带你学更多数据结构的知识

【数据结构（八）上】二叉树经典习题,数据结构,数据结构,二叉树

1.前言

在上一篇文章中，博主主要介绍了树与二叉树的基本概念、二叉树概念及特性、遍历方式自己实现一棵二叉树，在这篇文章中，博主将继续与大家分享二叉树经典习题。

2.经典习题

2.1相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同：OJ链接
解题思路

递归思想：
1.如果p为空，q为空，那么就是两颗空树肯定相等
2.如果一个树为空另一棵树不为空那么一定不相等
3.如果都不为空，值相同才相等。
4.在递归判断左子树是否相等，右子树是否相等，只有左右子树都相等才是相同的树

class Solution {
    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;
      }
  }
    public boolean isSameTree(TreeNode p, TreeNode q) {
         if(p==null&&q==null){
             return true;
         }
         //p、q有一个为空
         if(p==null&&q!=null||p!=null&&q==null){
             return false;
         }
         //两个都不为空，不相等
         if(p.val!=q.val){
             return false;
         }
         //两个都不为空且p=q
         return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

2.2另一棵子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树：OJ链接
解题思路

递归思想
1.如果其中一个为null那么就不是子树
2.如果是两棵相同的树，那么就为一定为子树
3.再递归看sub是否为左子树的子树，右子树的子树，如果都不是，则返回false

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null &&subRoot!=null|| subRoot == null&&root!=null) {
            return false;
        }
         if(isSameTree(root,subRoot)){
            return true;
        }        if(isSubtree(root.left,subRoot)){
            return true;
        }  if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }

2.3翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树：OJ链接
解题思路

1.判断是否为空树，判断这棵树是否只有根节点
2.再交换左右子树

public TreeNode invertTree(TreeNode root) {
         if(root==null||root.left==null&&root.right==null){
            return root;
        }
        TreeNode tmp= root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

2.4平衡二叉树

给定一个二叉树，判断它是否是平衡二叉树(左右子树相差不超过1)：OJ链接
解题思路

递归思想
1.先求一个树深度
2.求左子树的深度，再求右子树的深度，相差>1则不平衡
3.并且左子树和右子树的每一个个小树都要平衡

public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int left=MaxLength(root.left);
        int right=MaxLength(root.right);
        if (Math.abs(left-right)<=1&&isBalanced(root.right)&&isBalanced(root.left)){
            return true;
        }else {
            return false;
        }
    }
    public int MaxLength(TreeNode root){
        if (root==null){
            return 0;
        }
        int Left=MaxLength(root.left);
        int Right=MaxLength(root.right);
        return Left>Right?Left+1:Right+1;
    }

我们观察以上代码，我们发现在求长度的时候已经遍历了一次二叉树，但在求是否平衡的时候，每次递归又会再求高度再遍历数组，效率非常低。那有能不能在求高度的时候就可以判断子树是否平衡呢？答案是可以的，如下：

当求高度的时候先先判断左子树和右子树只差是否小于1，如果小于1就返回-1，就不会再往递归了。

public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return MaxLength(root)>0;
    }
    public int MaxLength(TreeNode root){
        if (root==null){
            return 0;
        }
        int Left=MaxLength(root.left);
        int Right=MaxLength(root.right);
       if(Left>=0&&Right>=0&&Math.abs(Left-Right)<=1){
           return Math.max(Left,Right)+1;
       }else return -1;
    }

2.5对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称：OJ链接
解题思路

1.判断root是否为null
2.比较左子树和右子树是否对称
3.若其中一棵树为null，那么不对称，若都为null则对称
4.再判断，左子树的左节点是否等于右子树的右节点&&左子树的右节点等于右子树的左节点，依次递归。

class Solution {
        public boolean isSymmetric(TreeNode root){
        if(root==null){
            return true;
        }else {
            return isSymmetric(root.left,root.right);
        }
    }
    public boolean isSymmetric(TreeNode L,TreeNode R){
        if(L==null&&R==null){
            return true;
        }
        if(L==null&&R!=null||L!=null&&R==null){
                return false;
        }
        if(L.val!= R.val){
            return false;
        }
      return isSymmetric(L.left,R.right)&&isSymmetric(L.right,R.left);
    }
}

2.6二叉树的构建及遍历

读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树：OJ链接

解题思路

1.遍历字符串，不为#，就new一个Node，但在遍历字符串的时候，我们要把i设置为成员变量防止每次递归后i从0开始
2.遍历二叉树中序输出

class TreeNode{
    char val;
    TreeNode left;
    TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}
public class Main {
    static int i=0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str=in.nextLine();
            TreeNode root= createTree(str);
            inOrder(root);
        }
    }
    public static TreeNode createTree(String str) {
//        for (int i=0;i<str.length();i++) {
//            char ch = str.charAt(i);i每次则从0开始
        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree(str);
            root.right=createTree(str);
        }else {
            i++;//不要担心i超出字符串长度的问题
        }
        return root;
    }
    public static void inOrder(TreeNode root){
        if(root==null){
            return ;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
}

2.7二叉树的分层遍历

分层遍历二叉树：OJ链接
解题思路

我们需要借助队列来实现，当root不为null时，那么我们将root入队，再将它出队打印，出对的时候我们添加左子树，添加右子树，循环上述操作，直到独队列为空。

public void order(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return;
        }
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.println(cur.val+" ");
            if(cur.left!=null){
                queue.add(cur.left);
            }
            if (cur.right!=null){
                queue.add(cur.right);
            }
        }

    }

除了递归的方式，还可以用非递归的方式：

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            List<Integer> l=new ArrayList<>();
            while (size!=0){
                TreeNode cur=queue.poll();
                size--;
                l.add(cur.val);
                if(cur.left!=null){
                    queue.add(cur.left);
                }
                if (cur.right!=null){
                    queue.add(cur.right);
                }
            }
            list.add(l);
        }
        return list;
    }