首页 > 代码库 > 平衡二叉树

平衡二叉树

1、求二叉树的深度  递归

  int BitreeDepth(TreeNode *root){

    if(root == NULL) return 0;

    else if(root->left == NULL && root->right == NULL) return 1;

    int DepthTl = BitreeDepth(root->left);

    int DepthTr = BitreeDepth(root->right);

    return 1+max(DepthTl,DepthTr);

  }

2、求是否为平衡二叉树 递归

  bool isBalanced(TreeNode *root){

    if(root == NULL)  return true;

    if(sub_abs(BitreeDepth(root->left),BitreeDepth(root->right))>1) return flase;

    return isBalanced(root->left)&&isBalanced(root->right);
  }

3、tips 递归的思想:找结束条件 然后return;如在2中求是否为平衡二叉树,我们第二个if,找结束条件是sub_abs()>1,而不是找运行条件sub_abs()<=1;

   暗示,在sub_abs()<=1的情况下,函数没有完成,继续找左子树和右子树,再 return。

  

平衡二叉树