专栏首页LeetCode判断一个树是否为平衡二叉树&&二分搜索树 && 完全二叉树
原创

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

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

解法一:

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

解法二:

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

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

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

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

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

    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. 如果两个孩子不是都有,那么后面遇到的节点必须都是叶子节点。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BST & AVL 二分搜索树 & 平衡二叉树的实现原理

    本文完整的实现了基本的BST,由于注重的是逻辑和原理的实现,所以没有采用泛型。注意方法的访问修饰符。

    大学里的混子
  • LeetCode 783 & 530 Distance Between BST Nodes

    Given a Binary Search Tree (BST) with the root node root, return the minimum dif...

    大学里的混子
  • 简单算法杂例

    第一:如果B栈为空,那么将A中的所有元素依次弹出后放入B栈中(负负为正,FILO顺序颠倒,再颠倒依次就为原始的顺序),此时B栈中已经有了元素,弹出的方式见“第二...

    大学里的混子
  • leetcode 110 Balanced Binary Tree

    Balanced Binary Tree Total Accepted: 63288 Total Submissions: 198315 My Submiss...

    用户1539362
  • leetcode: 114. Flatten Binary Tree to Linked List [✗]

    JNingWei
  • Golang Leetcode 671. Second Minimum Node In a Binary Tree.go

    更多内容请移步我的repo:https://github.com/anakin/golang-leetcode

    anakinsun
  • Redis+Twemproxy分片存储实现

    Redis的安装这里不再多讲,相关步骤可从官网或其它渠道得到。为安装redis多实例,这里简单提前创建完相关文件夹。其中redis存放应用程序,redis1/r...

    歪脖贰点零
  • 十大经典排序算法(Python代码实现)

    排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

    用户2769421
  • 用Python手写十大经典排序算法

    来源 | https://github.com/hustcc/JS-Sorting-Algorithm

    AI科技大本营
  • 用 Python 手写十大经典排序算法

    来源:https://github.com/hustcc/JS-Sorting-Algorithm

    统计学家

扫码关注云+社区

领取腾讯云代金券