关于平衡二叉树优化算法


这是在 geeksforgeeks 上找到的关于平衡二叉树的优化算法,思路是在递归求深度的同时判断是否是平衡二叉树,解决了求深度的时候递归返回值的问题,但是还是不太理解那两行递归具体是怎么调用的?问题在注释中


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

/* The function returns true if root is balanced else false
   The second parameter is to store the height of tree.  
   Initially, we need to pass a pointer to a location with value 
   as 0. We can also write a wrapper over this function */
bool isBalanced(struct node *root, int* height)
{
  /* lh --> Height of left subtree 
     rh --> Height of right subtree */   
  int lh = 0, rh = 0;  

  /* l will be true if left subtree is balanced 
    and r will be true if right subtree is balanced */
  int l = 0, r = 0;

  if(root == NULL)
  {
    *height = 0;
     return 1;
  }

  /* Get the heights of left and right subtrees in lh and rh 
    And store the returned values in l and r */   
  l = isBalanced(root->left, &lh);  
  r = isBalanced(root->right,&rh);
 //1.既然递归结束的条件是第一参数为NULL,那么l,r最终不都应该return true了吗?
 //2.lh,rh一直处于递归函数中,每次都被赋值成0,他们的值是怎么改变的?
  /* Height of current node is max of heights of left and 
     right subtrees plus 1*/   
  *height = (lh > rh? lh: rh) + 1;

  /* If difference between heights of left and right 
     subtrees is more than 2 then this node is not balanced
     so return 0 */
  if((lh - rh >= 2) || (rh - lh >= 2))
    return 0;

  /* If this node is balanced and left and right subtrees 
    are balanced then return true */
  else return l&&r;
}

二叉树 递归 数据结构和算法 C++ c

变研的熊猫 10 years ago

1.既然递归结束的条件是第一参数为NULL,那么l,r最终不都应该return true了吗?

只有 最深 的那一层递归返回 1 吧? 下面注释写的非常清楚,如果 左右高度不等,差距大于2 ,返回 0.

2.lh,rh一直处于递归函数中,每次都被赋值成0,他们的值是怎么改变的?

这个,你是不是看糊涂了呢? lh 和 rh 进入递归后,名字是 height,其改变的地方就在你问题的下面。。。


 *height = (lh > rh? lh: rh) + 1;


个人认为,题主应该是没明白递归的基本概念,建议温习一下基础的递归知识。

noix猪君 answered 10 years ago

Your Answer