关于平衡二叉树优化算法

Question

这是在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;
}

Answer 1

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

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

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

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

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

---

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