关于平衡二叉树优化算法
这是在 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;
}
变研的熊猫
10 years, 1 month ago
Answers
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, 1 month ago