常见的二叉树问题
1.判定二叉树是否是完全二叉树
public boolean isCBT(TreeNode root){
if(root==null){
return true;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
boolean flag=false;
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;i<size;i ){
TreeNode cur=queue.poll();
if(flag&&(cur.left!=null||cur.right!=null)){
return false;
}
if(cur.left==null&&cur.right!=null){
return false;
}
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}else{
flag=true;
}
}
}
return true;
}
2.二叉树层序遍历
/**
* 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 List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret=new LinkedList<>();
if(root==null){
return ret;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> leve=new LinkedList<>();
int size=queue.size();
for(int i=0;i<size;i ){
TreeNode cur=queue.poll();
leve.add(cur.val);
if(cur.left!=null){
queue.add(cur.left);
}
if(cur.right!=null){
queue.add(cur.right);
}
}
ret.add(leve);
}
return ret;
}
}
3.判定一个二叉树是否是对称
/**
* 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 isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return sameTree(root.left,root.right);
}
public boolean sameTree(TreeNode root1,TreeNode root2){
if(root1==null&&root2==null){
return true;
}
if(root1==null||root2==null){
return false;
}
if(root1.val!=root2.val){
return false;
}
return sameTree(root1.left,root2.right)&&sameTree(root1.right,root2.left);
}
}
4.判定一个二叉树是否是平衡二叉树
/**
* 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 isBalanced(TreeNode root) {
if(root==null){
return true;
}
Map<TreeNode,Integer> map=new HashMap<>();
int leftHeight=0;
int rightHeight=0;
if(map.containsKey(root.left)){
leftHeight=map.get(root.left);
}else{
leftHeight=height(root.left);
map.put(root.left,leftHeight);
}
if(map.containsKey(root.right)){
rightHeight=map.get(root.right);
}else{
rightHeight=height(root.right);
map.put(root.right,rightHeight);
}
int abs=Math.abs(leftHeight-rightHeight);
if(abs>1){
return false;
}
return isBalanced(root.left)&&isBalanced(root.right);
}
public int height(TreeNode root){
if(root==null){
return 0;
}
return 1 Math.max(height(root.left),height(root.right));
}
}
5.求二叉树的高度
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return 1 Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
6.判定两个二叉树是否是包含关系
/**
* 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 isSubtree(TreeNode root, TreeNode subRoot) {
if(root==null&&subRoot==null){
return true;
}
if(root==null||subRoot==null){
return false;
}
if(sameTree(root,subRoot)){
return true;
}
return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
}
public boolean sameTree(TreeNode root1,TreeNode root2){
if(root1==null&&root2==null){
return true;
}
if(root1==null||root2==null){
return false;
}
if(root1.val!=root2.val){
return false;
}
return sameTree(root1.left,root2.left)&&sameTree(root1.right,root2.right);
}
}
7.比较两个二叉树是否相同
/**
* 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){
return false;
}
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
这篇好文章是转载于：学新通技术网
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 学新通技术网
- 本文地址： /boutique/detail/tanhgggcjb
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13
