1.判定二叉树是否是完全二叉树
public boolean isCBT(TreeNode root){
if(root==null){
return true;
}
Queue
queue.offer(root);
boolean flag=false;
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;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.二叉树层序遍历 class Solution { public List List if(root==null){ return ret; } Queue queue.offer(root); while(!queue.isEmpty()){ List int size=queue.size(); for(int i=0;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.判定一个二叉树是否是对称 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.判定一个二叉树是否是平衡二叉树 class Solution { public boolean isBalanced(TreeNode root) { if(root==null){ return true; } Map 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.求二叉树的高度 class Solution { public int maxDepth(TreeNode root) { if(root==null){ return 0; } return 1+Math.max(maxDepth(root.left),maxDepth(root.right)); } } 6.判定两个二叉树是否是包含关系 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.比较两个二叉树是否相同 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); } }
