西安咪豆网站建设公司,轻骑铃木摩托车官网,北京市工程信息网,网络营销与管理专业Java二叉树面试题讲解#x1f697;1.检查两颗树是否相同#x1f695;2.另一颗树的子树#x1f699;3.二叉树最大深度#x1f68c;4.判断一颗二叉树是否是平衡二叉树#x1f68e;5.对称二叉树#x1f693;6.获取树中结点个数#x1f691;7.判断一个树是不是完全二叉树1.检查两颗树是否相同2.另一颗树的子树3.二叉树最大深度4.判断一颗二叉树是否是平衡二叉树5.对称二叉树6.获取树中结点个数7.判断一个树是不是完全二叉树大家好我是晓星航。今天为大家带来的是 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编号一返回值2316。
7.判断一个树是不是完全二叉树
boolean isCompleteTree(BTNode root) {if (root null) {return true;}QueueBTNode 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的右节点去掉 则我们的二叉树变为了完全二叉树 感谢各位读者的阅读本文章有任何错误都可以在评论区发表你们的意见我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞你的每一次鼓励都是作者创作的动力哦
