剑指OFFER-平衡二叉树

QuestionSolution递归

Question

输入一棵二叉树，判断该二叉树是否是平衡二叉树。 关键词：二叉树 深度 递归

Solution

这题简直是二叉树深度的更新版，不仅要知道当前深度，还要判断左右深度差不能超过1。虽然既要返回深度也要返回判断，不好写函数的返回值，干脆设置深度为-1时代表否定，那么在递归中要时刻判断是否为-1，是就结束递归。

递归

时间复杂度：O() 空间复杂度：O()

Python class Solution: def IsBalanced_Solution(self, pRoot): if not pRoot: return True def depth(p): if not p: return 0 left = depth(p.left) if left == -1: return -1 right = depth(p.right) if right == -1: return -1 return max(left, right)+1 if abs(left-right)<=1 else -1 return depth(pRoot)!= -1 C++ class Solution { public: bool IsBalanced_Solution(TreeNode* pRoot) { if(!pRoot) return true; return depth(pRoot)!=-1; } int depth(TreeNode* p){ if(!p) return 0; int d_left = depth(p->left); if(d_left==-1) return -1; int d_right = depth(p->right); if(d_right==-1) return -1; return abs(d_left - d_right)<=1? max(d_left, d_right)+1:-1; } };