欢迎光临
我们一直在努力

二叉树的例题练习 检查两颗树是否相同 && 另一颗树的子树 && 翻转二叉树 && 平衡二叉树

例题

1. 检查两颗树是否相同

遍历两个二叉树

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){//判断节点上val是否相同
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}

另一颗树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

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){//判断节点上val是否相同
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
//判断是否是子树
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//当root为空说明root遍历完也没有找到与subRoot相同
if(root == null){
return false;
}
return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
}

翻转二叉树

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。 在这里插入图片描述

class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode newroot = root.left;
root.left = root.right;
root.right = newroot;
invertTree(root.left);
invertTree(root.right);
return root;
}
}

  • 左枝与右枝交换
  • 左树翻转
  • 右树翻转

平衡二叉树

平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。

  • 将每一个节点的高度放入自己的val存储后向上传递

class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
if(!isBalanced(root.left)){
return false;
}
if(!isBalanced(root.right)){
return false;
}
if(root.left == null && root.right == null){
root.val = 1;
return true;
}
if(root.left == null || root.right == null){
if(root.left == null && root.right.val < 2){
root.val = 2;
return true;
}
if(root.right == null && root.left.val < 2){
root.val = 2;
return true;
}
return false;
}
if(Math.abs(root.left.val – root.right.val) < 2){
root.val = Math.max(root.left.val,root.right.val) + 1;
return true;
}
return false;
}
}

代码优化后

class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
// 先递归校验左右子树是否平衡
if(!isBalanced(root.left)) return false;
if(!isBalanced(root.right)) return false;

// 叶子节点,高度赋值为1
if(root.left == null && root.right == null){
root.val = 1;
return true;
}

// 单侧为空的节点
if(root.left == null || root.right == null){
int h = root.left == null ? root.right.val : root.left.val;
if(h < 2){
root.val = h + 1;
return true;
}
return false;
}

// 左右都存在,计算高度差
int leftH = root.left.val;
int rightH = root.right.val;
if(Math.abs(leftH – rightH) < 2){
// 修正max参数错误
root.val = Math.max(leftH, rightH) + 1;
return true;
}
return false;
}
}

在这里插入图片描述

赞(0)
未经允许不得转载:171主机测评 » 二叉树的例题练习 检查两颗树是否相同 && 另一颗树的子树 && 翻转二叉树 && 平衡二叉树
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址