前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >判断一个树是否为平衡二叉树&&二分搜索树 && 完全二叉树

判断一个树是否为平衡二叉树&&二分搜索树 && 完全二叉树

原创
作者头像
大学里的混子
修改2019-02-20 14:51:25
1.2K0
修改2019-02-20 14:51:25
举报
文章被收录于专栏:LeetCode

一、判断一个树是否为平衡二叉树

解法一:

代码语言:javascript
复制
   public boolean isBalanced(TreeNode root) {
       if (root == null) return true;
       if (Math.abs(treeHeight(root.right)-treeHeight(root.left ))>1) return false;
       return isBalanced(root.left)&&isBalanced(root.right);
    }

    public int treeHeight(TreeNode root){
        if (root == null) return 0;
        return 1+Math.max(treeHeight(root.left),treeHeight(root.right));
    }

解法二:

代码语言:javascript
复制

public boolean isBalanced(TreeNode root) {
    return process(root).isBalance;
}
    
public static class ReturnData{
    boolean isBalance;
    int height;
    public ReturnData(boolean isBalance, int height) {
        this.isBalance = isBalance;
        this.height = height;
    }
}

public static ReturnData process(TreeNode root){
     if (root == null ) return new ReturnData(true,0);
     ReturnData left = process(root.left);
     if (!left.isBalance) return new ReturnData(false,0);
     ReturnData right = process(root.right);
     if (!right.isBalance) return new ReturnData(false,0);
     if ( Math.abs(left.height - right.height)>1) return new ReturnData(false,0);
     return new ReturnData(true,Math.max(left.height,right.height)+1);
}

二、判断一个树是否为二分搜索树

只要中序遍历是递增的就是搜索二叉树。这里采用的是前面文章采用的二叉树非递归的方式遍历的方法。

代码语言:javascript
复制
   public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while ( root != null || !stack.isEmpty()){
            if (root == null){
                TreeNode temp = stack.pop();
                if (pre != null){
                    if (temp.val <= pre.val) return false;
                }
                pre = temp;
                root = temp.right;
            }else {
                stack.push(root);
                root = root.left;
            }
        }
        return true;
    }

三、判断一个二叉树是不是完全二叉树

代码语言:javascript
复制
    public boolean isCompleteTree(TreeNode root) {
        if (root == null ) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            if ((temp.left == null && temp.right != null) || 
                (leaf && (temp.left != null || temp.right != null))){
                return false;
            }
            if (temp.left == null || temp.right == null) {
                leaf = true;
            }
            if ( temp.left != null){
                queue.offer(temp.left);
            }
            if ( temp.right != null ){
                queue.offer(temp.right);
            }
        }
        return true;
    }

这里存在两个逻辑:

  1. 有右孩子但是没有左孩子,那么直接false
  2. 如果两个孩子不是都有,那么后面遇到的节点必须都是叶子节点。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、判断一个树是否为平衡二叉树
    • 解法一:
      • 解法二:
      • 二、判断一个树是否为二分搜索树
      • 三、判断一个二叉树是不是完全二叉树
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档