常见的二叉树问题

常见的二叉树问题

1.判定二叉树是否是完全二叉树

public boolean isCBT(TreeNode root){

if(root==null){

return true;

}

Queue queue=new linkedList<>();

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> levelOrder(TreeNode root) {

        List> ret=new linkedList<>();

        if(root==null){

            return ret;

        }

        Queue queue=new linkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){

            List leve=new linkedList<>();

            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 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.求二叉树的高度

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);

    }

}