Java二叉树面试题讲解

2023-07-19 281

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Java二叉树面试题讲解

Java二叉树面试题讲解

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

🚗1.检查两颗树是否相同

检查两颗树是否相同。OJ链接

/**
 * 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) {
            return true;
        }
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

思路：

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

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

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

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

🚕2.另一颗树的子树

另一颗树的子树OJ链接

/**
 * 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的左子树或者右子树

🚙3.二叉树最大深度

二叉树最大深度OJ链接

/**
 * 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 maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }   
}

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

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

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

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函数中的绝对值函数，目的是返回一个正的差值。

🚎5.对称二叉树

对称二叉树OJ链接

/**
 * 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);
    }
}

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

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

🚓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;
}

思路：法二的思路和上图一样，例如在二编号返回值时，它的值为编号三返回的值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;
}

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

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

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

Java二叉树面试题讲解

Java二叉树面试题讲解

🚗1.检查两颗树是否相同

🚕2.另一颗树的子树

🚙3.二叉树最大深度

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

🚎5.对称二叉树

🚓6.获取树中结点个数

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

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

Java二叉树面试题讲解

Java二叉树面试题讲解

🚗1.检查两颗树是否相同

🚕2.另一颗树的子树

🚙3.二叉树最大深度

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

🚎5.对称二叉树

🚓6.获取树中结点个数

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

热门文章

最新文章

相关课程

相关电子书