Java二叉树面试题讲解

小咪咪 2024-04-28 07:36 96阅读 0赞

#### Java二叉树面试题讲解 ####

*  ?1.检查两颗树是否相同
 *  ?2.另一颗树的子树
 *  ?3.二叉树最大深度
 *  ?4.判断一颗二叉树是否是平衡二叉树
 *  ?5.对称二叉树
 *  ?6.获取树中结点个数
 *  ?7.判断一个树是不是完全二叉树：

**大家好，我是晓星航。今天为大家带来的是 Java二叉树面试题讲解 的讲解！?**

## ?1.检查两颗树是否相同 ##

检查两颗树是否相同。[OJ链接][OJ]![202303240951864.png][]

![202303240951910.png][] ![202303240951271.png][]

思路：

1.先判断p和q是否都为空，返回true。

2.在判断p和q是否一个为空一个不为空，返回false。

3.然后再判断p的值和q的值相不相等，相等返回true，不相等返回false。

4.最后返回p和q的左节点以及右节点是否都满足位置一致且数值相同，即直接递归判断(让之后的结点重新进入我们的函数)。

![202303240952206.png][]

## ?2.另一颗树的子树 ##

另一颗树的子树[OJ链接][OJ 1]![202303240952026.png][]![202303240952200.png][]![202303240953326.png][]![202303240953830.png][]

/**
     * Definition for a binary tree node.
     * public 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;
     *     }
     * }
     */
    class Solution {
        
            public boolean isSameTree(TreeNode p, TreeNode q) {
        
            if (p == null && q != null || p != null && q == null) {
        
                return false;
            }
            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);
        }
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
            if (root == null || subRoot == null) {
        
                return false;
            }
            //根节点和subRoot是不是两颗相同的树
            if (isSameTree(root,subRoot)) {
        
                return true;
            }
            //subRoot是不是root的左子树
            if (isSubtree(root.left,subRoot)) {
        
                return true;
            }
            //subRoot是不是root的右子树
            if (isSubtree(root.right,subRoot)) {
        
                return true;
            }
            return false;
        }
    }

思路：

1、先判断两棵树是不是两颗相同的子树

2、如果不是，那么分别判断subRoot是不是root的左子树或者右子树

![202303240953974.png][]

## ?3.二叉树最大深度 ##

二叉树最大深度[OJ链接][OJ 2]

![202303240955930.png][]

思路：通过创建左树高度`leftHeight`与右树高度`rightHeight`来进行比较，并返回较大值加1给上一层函数作为结果，在最下层元素的左右结点都为null直接返回，并多次递归后，直到返回到开始的root结点的值即为我们此树的高度。

![202303240956028.png][] ![202303241011972.png][]

## ?4.判断一颗二叉树是否是平衡二叉树 ##

判断一颗二叉树是否是平衡二叉树[OJ链接][OJ 3]

![202303241000232.png][] ![202303241000577.png][] ![202303241000283.png][]

> 1、root左树的高度-右树的高度<=1  
> 2、root的左树是平衡点，右树是平衡的

/**
     * Definition for a binary tree node.
     * public 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;
     *     }
     * }
     */
    class Solution {
        
        public int height(TreeNode root) {
        
            if(root == null) {
        
                return 0;
            }
            int leftHeight = height(root.left);
            int rightHeight = height(root.right);
            //return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
            if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {
        
                return Math.max(leftHeight,rightHeight) + 1;
            } else {
        
                //说明不平衡
                return -1;
            }
        }
        /**
        *时间复杂度：O(N)
        */
        public boolean isBalanced(TreeNode root) {
        
            if (root == null) {
        
                return true;
            }
            //int left = height(root.left);
            //int right = height(root.right);
            //return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
            return height(root) >= 0;
        }
    }

思路：通过平衡二叉树的性质：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1来确定我们函数的返回值从而递归。注释代码是分开实现的方法，没有注释的代码是在判断高度的时候就判断该二叉树是不是平衡二叉树如果不是则返回-1，然后加入逻辑只要`leftHeight`与`rightHeight`不>=0则返回-1，提高平衡树判断效率。

注：Math.abs()是调用的Math函数中的绝对值函数，目的是返回一个正的差值。

![202303241001213.png][]

## ?5.对称二叉树 ##

对称二叉树[OJ链接][OJ 4]

![202303241005790.png][] ![202303241006103.png][]

/**
     * Definition for a binary tree node.
     * public 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;
     *     }
     * }
     */
    class Solution {
        
        public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        
            if (leftTree == null && rightTree != null ||leftTree != null && rightTree == null) {
        
                return false;
            }
            if (leftTree == null && rightTree == null) {
        
                return true;
            }
            if (leftTree.val != rightTree.val) {
        
                return false;
            }
            return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);
        }
            public boolean isSymmetric(TreeNode root) {
        
            if (root == null) {
        
                return true;
            }
            return isSymmetricChild(root.left,root.right);
        }
    }

思路：二叉树的对称可以理解为镜像对称，即左节点的左和右节点的右 左节点的右和右节点的左是否对称，

他和判断两个二叉树是否相同很类似，然后返回值返回左节点的左和右节点的右 左节点的右和右节点的左递归即可。

![202303241006697.png][]

## ?6.获取树中结点个数 ##

法一：

int count = 0;
    int size1(BTNode root) {
        
        if (root == null) {
        
            return 0;
        }
        count++;
        size1(root.left);
        size1(root.right);
        return count;
    }

运用子问题思路来调用递归返回树的总结点个数。

法二：

int count = 0;
    int size2(BTNode root) {
        
        if (root == null) {
        
            return 0;
        }
        return size2(root.left) + size2(root.right) + 1;
    }

![202303241007896.png][]

思路：法二的思路和上图一样，例如在 二编号 返回值时，它的值为 编号三 返回的值1加上本身的1，所以 编号二 的值就返回2，同理编号四返回值为3，编号一返回值2+3+1=6。

## ?7.判断一个树是不是完全二叉树： ##

boolean isCompleteTree(BTNode root) {
        
        if (root == null) {
        
            return true;
        }
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
        
            BTNode cur = queue.poll();
            if (cur != null) {
        
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
        
                break;
            }
        }
        while (!queue.isEmpty()) {
        
            BTNode top = queue.peek();
            if (top != null) {
        
                return false;
            }
            queue.poll();
        }
        return true;
    }

![202303241008567.png][]

由上图关系得我们的二叉树不是完全二叉树

![202303241008450.png][]

如下图如果我们将E的右节点去掉 则我们的二叉树变为了完全二叉树

![202303241009667.png][] ![202303241009918.png][] ![202303241011477.png][]

*感谢各位读者的阅读，本文章有任何错误都可以在评论区发表你们的意见，我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞，你的每一次鼓励都是作者创作的动力哦！?*

[OJ]: https://leetcode.cn/problems/same-tree/
[202303240951864.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/e3cb9ab4ca464a50b2ed3fda304e7252.png
[202303240951910.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303240951910.png
[202303240951271.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/f3efe50e24b5464e9b11b79bdc6a8557.png
[202303240952206.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/7eb0b866ca8a45afb713911565be1f7a.png
[OJ 1]: https://leetcode.cn/problems/subtree-of-another-tree/
[202303240952026.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303240952026.png
[202303240952200.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303240952200.png
[202303240953326.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303240953326.png
[202303240953830.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/f9a5433176574068bc4e836726363338.png
[202303240953974.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/33f7deeed48245f09794e223c30b1b82.png
[OJ 2]: https://leetcode.cn/problems/maximum-depth-of-binary-tree/
[202303240955930.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/79a7d94d67e44c1f92932cb2009bab9e.png
[202303240956028.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303240956028.png
[202303241011972.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/8f306135fc234bf7a56793148b2d8f5f.png
[OJ 3]: https://leetcode.cn/problems/balanced-binary-tree/
[202303241000232.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303241000232.png
[202303241000577.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303241000577.png
[202303241000283.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/93ad5ca8b70d4228b5bcc5f2c90beb90.png
[202303241001213.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/2ac189d847034a8f88293b073740eb25.png
[OJ 4]: https://leetcode.cn/problems/symmetric-tree/
[202303241005790.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303241005790.png
[202303241006103.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/d8d98bb0f6474094b57822d55221ab82.png
[202303241006697.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/3c1dcb5f17f74f04a6689f3ecace9c19.png
[202303241007896.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/c2947ad339774c9b9f66e495ccf2460b.png
[202303241008567.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/d45fe0e1dda5423488c4ba7d860f516f.png
[202303241008450.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/07ad96bdb6de4028bd9e214d3d157924.png
[202303241009667.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303241009667.png
[202303241009918.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303241009918.png
[202303241011477.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/b1a5d902b10242ac8ec679e6a86c6599.png