Leetcode:balanced_binary_tree

Leetcode:balanced_binary_tree

一、 題目

判斷給定的二叉樹是否是平衡二叉樹，即每一個節點的深度相差不大於1

二、 分析

對於樹的問題，我們一般都會想到遞歸，這道題也一樣。我們只需要判斷每一個節點的左右子樹是否平衡即可。

遞歸，遞歸，遞歸……

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode *root) 
	{
		if(depthcheck(root)==0)
			return true;
		if(abs(depthcheck(root->left)-depthcheck(root->right))>1)
			return false;
		else
			return isBalanced(root->left) && isBalanced(root->right);
	}
 
	int depthcheck(TreeNode *root)
	{
		if(!root)
			return 0;
		int depthL=depthcheck(root->left)+1;
		int depthR=depthcheck(root->right)+1;
		return depthL > depthR ? depthL : depthR;
	}
};