当前位置: 首页> 财经> 金融 > 个性化网站设计_重庆seo代理计费_网站怎样被百度收录_惠州seo代理

个性化网站设计_重庆seo代理计费_网站怎样被百度收录_惠州seo代理

时间:2025/7/11 0:30:40来源:https://blog.csdn.net/xiaochuan_bsj/article/details/142371391 浏览次数:0次
个性化网站设计_重庆seo代理计费_网站怎样被百度收录_惠州seo代理

目录

判断树是否相同

判断树是不是另一棵树的子树

二叉树翻转

判断平衡二叉树

 二叉树层序遍历


这篇主要提供一些关于二叉树例题的讲解,如果对二叉树及其基本操作有疑问的可以转至:

二叉树(上)-CSDN博客
二叉树(中)-CSDN博客

判断树是否相同

力扣链接:100. 相同的树 - 力扣(LeetCode)

题目描述:

给你两棵二叉树的根节点 p 和 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);

完整代码为

//时间复杂度, min(p, q)
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//1.先判断结构是否相同if(p != null && q == null || p == null && q != null){return false;}//2.剩下的两种情况为 空或者相等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);}
}

判断树是不是另一棵树的子树

力扣链接:572. 另一棵树的子树 - 力扣(LeetCode)

情况可以大致分为以下三种:

 思路为:

  1. 当前子树和根节点是否一样?
  2. 判断子树是不是和当前root的左子树一样?
  3. 判断子树是不是和当前root的右子树一样?

这里其实也调用了上面写的 判断树是否相同 的代码,

先用 root 和 subRoot(子树) 进行判断树是否相同,然后用root的左子树和右子树同subroot进行递归比较,分别进行比较和返回。

注意:先是比较两棵树是否为子树关系,然后进行递归。

//时间复杂度
//root共有节点r个,subRoot共有节点s个
//时间复杂度为O(r * s)
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(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;}public boolean isSameTree(TreeNode p, TreeNode q) {//1.先判断结构是否相同if(p != null && q == null || p == null && q != null){return false;}//2.剩下的两种情况为 空或者相等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);}}

二叉树翻转

力扣链接:226. 翻转二叉树 - 力扣(LeetCode)

 

 主要思路其实和数据的交换位置是一个类型的,像是下面的代码部分

        TreeNode tmp = root.left;root.left = root.right;root.right = tmp;

然后进行递归,同时加上递归条件和特定情况

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null){return root;}//避免叶子节点再进行if(root.left == null && root.right == null){return null;}TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;}
}

判断平衡二叉树

力扣链接:110. 平衡二叉树 - 力扣(LeetCode)

平衡二叉树:如果一棵树是二叉树,那么它的每棵子树都是平衡二叉树。

左右子树高度差 <=1;如果 >=2 则不是平衡二叉树

思路:遍历这棵树的节点,求每个节点的左树和右树的高度,如果发现h >=2,则返回false。

判断整棵树会发现根节点的左子树为平衡二叉树,右子树也是平衡二叉树。

 这里可以先尝试把框架搭建出来:求左子树的高度和右子树的高度,

    public boolean isBalanced(TreeNode root) {if(root == null){return true;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return Math.abs(leftHeight - rightHeight) < 2&& isBalanced(root.left) && isBalanced(root.right);}

因为要求每棵树的左右树高,所以我们需写一个额外的方法来进行。

    public int getHeight(TreeNode root){if(root == null){return 0;}int leftTree = getHeight(root.left);int rightTree = getHeight(root.right);return leftTree > rightTree ? leftTree + 1 : rightTree +1;}

完整代码为

//时间复杂度为O(N^2)
class Solution {public boolean isBalanced(TreeNode root) {if(root == null){return true;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return Math.abs(leftHeight - rightHeight) < 2&& isBalanced(root.left) && isBalanced(root.right);}public int getHeight(TreeNode root){if(root == null){return 0;}int leftTree = getHeight(root.left);int rightTree = getHeight(root.right);return leftTree > rightTree ? leftTree + 1 : rightTree +1;}
}

 二叉树层序遍历

力扣链接:102. 二叉树的层序遍历 - 力扣(LeetCode)

第一种方法:队列

思路:主要是依靠队列来实现层序遍历,先把头节点设为cur,询问队列时候为空,再去除头节点,并输出,若左右子树不为则分别放入左右子树 

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

第二种方法:队列 + 二维数组 

也就是力扣链接里的题目,它主要是让我们把每一层的数据放在一起,这里我们可以通过定义一个size变量,来记录每一层数据的个数。

public List<List<Integer>> levelOrder2(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> list = new ArrayList<>();while (size != 0) {TreeNode cur = queue.poll();list.add(cur.val);//System.out.print(cur.val + " ");if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}ret.add(list);}return ret;
}

关键字:个性化网站设计_重庆seo代理计费_网站怎样被百度收录_惠州seo代理

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: