时间戳

首页 > 解决方案 > 为什么这个检查平衡二叉树的实现是错误的

data-structures - 为什么这个检查平衡二叉树的实现是错误的

问题描述

public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int rightCount = maxDepth(root.right);
        int leftCount = maxDepth(root.left);
        if(Math.abs(rightCount-leftCount)<=1) return true;
        return false;
    }
    public int maxDepth(TreeNode root){
       if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }

检查两个分支的最大深度并确定绝对值是否 <=1

标签： data-structurestreebinary-tree

解决方案

首先：

如果您有无效的根参数isBalanced返回true，那么这是一个糟糕的实现，尽管代码可能没有错误。

在我看来，函数应该使用有效的参数，否则抛出异常（错误？）。

还要检查这个解决方案，阅读代码并尝试做这样的事情：

/* C program to check if a tree is height-balanced or not */
#include <stdio.h> 
#include <stdlib.h> 
#define bool int 
  
/* A binary tree node has data, pointer to left child 
   and a pointer to right child */
struct node { 
    int data; 
    struct node* left; 
    struct node* right; 
}; 
  
/* Returns the height of a binary tree */
int height(struct node* node); 
  
/* Returns true if binary tree with root as root is height-balanced */
bool isBalanced(struct node* root) 
{ 
    int lh; /* for height of left subtree */
    int rh; /* for height of right subtree */
  
    /* If tree is empty then return true */
    if (root == NULL) 
        return 1; 
  
    /* Get the height of left and right sub trees */
    lh = height(root->left); 
    rh = height(root->right); 
  
    if (abs(lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right)) 
        return 1; 
  
    /* If we reach here then tree is not height-balanced */
    return 0; 
} 
  
/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
  
/* returns maximum of two integers */
int max(int a, int b) 
{ 
    return (a >= b) ? a : b; 
} 
  
/*  The function Compute the "height" of a tree. Height is the 
    number of nodes along the longest path from the root node 
    down to the farthest leaf node.*/
int height(struct node* node) 
{ 
    /* base case tree is empty */
    if (node == NULL) 
        return 0; 
  
    /* If tree is not empty then height = 1 + max of left 
      height and right heights */
    return 1 + max(height(node->left), height(node->right)); 
} 
  
/* Helper function that allocates a new node with the 
   given data and NULL left and right pointers. */
struct node* newNode(int data) 
{ 
    struct node* node = (struct node*) 
        malloc(sizeof(struct node)); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 
  
    return (node); 
} 
  
int main() 
{ 
    struct node* root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
    root->left->left->left = newNode(8); 
  
    if (isBalanced(root)) 
        printf("Tree is balanced"); 
    else
        printf("Tree is not balanced"); 
  
    getchar(); 
    return 0; 
}

（从这里复制并粘贴）

推荐阅读