Balanced Binary Tree 判断是否为平衡二叉树 解法集合

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees ofeverynode never differ by more than

1 参数传递法：

bool isBalanced(TreeNode *root) {
		if(!root) return true;
		bool balance = true;
		balanceHelper(root, balance);
		return balance;
	}

	void treeHeight(TreeNode *node, int &h, int oneh = 0)
	{
		if(!node) return;
		oneh++;
		treeHeight(node->left, h, oneh);
		treeHeight(node->right, h, oneh);
		if(!node->left && !node->right)
			h = oneh > h? oneh:h;
	}

	void balanceHelper(TreeNode *node, bool &balance)
	{
		if(!balance || !node) return;
		int lh = 0;
		int rh = 0;
		treeHeight(node->left, lh);
		treeHeight(node->right, rh);
		if (abs(lh-rh) > 1) 
		{
			balance = false;
			return;
		}
		balanceHelper(node->left, balance);
		balanceHelper(node->right, balance);
	}

2 返回值：

bool isBalanced2(TreeNode *root) {
		if (root == nullptr) return true;

		int left = getHeight(root->left);
		int right = getHeight(root->right);
		if (abs(left - right) > 1) return false;

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

	int getHeight(TreeNode *n) {
		if (n == nullptr) return 0;
		return max(getHeight(n->left), getHeight(n->right)) + 1;
	}

3 加判断：

int cntHeight(TreeNode *root) {
		if(root == NULL) return 0;
		int l = cntHeight(root->left);
		int r = cntHeight(root->right);
		if(l < 0 || r < 0 || abs(l-r) > 1) return -1;
		else  return max(l, r) + 1;
	}
	bool isBalanced3(TreeNode *root) {
		if(root == NULL) return true;    
		int l = cntHeight(root->left);
		int r = cntHeight(root->right);
		if(l < 0 || r < 0 || abs(l-r) > 1) return false;
		else return true;
	}

4 其实可以更加简单：

bool isBalanced5(TreeNode *root) {
		return (height_(root) >= 0 );
		//or: return cntHeight(root) >=0;
	}

	int height_(TreeNode *root){
		if (root == NULL) return 0;
		int lh = height_(root->left);
		if (lh == -1 ) return lh;
		int rh = height_(root->right);
		if (rh == -1 ) return rh;

		int d = rh - lh;
		if (d > 1 || d < -1) return -1;
		else return 1 + ( d > 0 ? rh : lh );
	}

5 或者：

bool isBalanced(TreeNode *root) {
		return height(root) != -1;
	}

	int height(TreeNode *root)
	{
		if(root == nullptr)
			return 0;

		int leftHeight = height(root->left);
		if(leftHeight == -1)
			return -1;

		int rightHeight = height(root->right);
		if(rightHeight == -1)
			return -1;

		if(abs(leftHeight - rightHeight) > 1)
			return -1;

		return 1 + max(leftHeight, rightHeight);
	}

6 还有：

bool f(TreeNode *root, int &d) {
		if (!root) {
			d = 0;
			return true;    
		}
		int ld, rd;
		bool lb = f(root->left, ld);
		bool rb = f(root->right, rd);
		d = ld > rd ? ld+1:rd+1;
		if (abs(ld-rd)>1) return false;
		return lb && rb;
	}
	bool isBalanced8(TreeNode *root) {
		// Note: The Solution object is instantiated only once and is reused by each test case.
		int depth;
		return f(root, depth);
	}

部分程序出处：

LeetCode

2014-1-17 update

bool isBalanced(TreeNode *root) 
	{
		if (!root) return true;
		if (!isBalanced(root->left)) return false;
		if (!isBalanced(root->right)) return false;
		if (abs(treeDepth(root->left)-treeDepth(root->right)) > 1) 
			return false;
		return true;
	}
	int treeDepth(TreeNode *r)
	{
		if (!r) return 0;
		return max(treeDepth(r->left), treeDepth(r->right)) +1;
	}