非递归方式
class Solution { public: bool hasNoChildren(TreeNode* node) { if (!node->left && !node->right) return true; return false; } int getHeight(TreeNode* root){ if(root == NULL) return 0;//如果节点为空高度为0 int lh = getHeight(root->left);//返回左子树高度 int rh = getHeight(root->right);//返回右子树高度 return max(lh,rh) + 1; //取左子树和右子树高度中最大的并且+1 } bool IsBalanced_Solution(TreeNode* pRoot) { if (!pRoot) return true; queue<TreeNode*> q; q.push(pRoot->left); q.push(pRoot->right); while (!q.empty()) { TreeNode* pre = q.front(); q.pop(); TreeNode* pro = q.front(); q.pop(); //左右子树都为空 if (!pre && !pro) continue; //左右子树只有一个是空 if (!pre || !pro) { if (pre) return hasNoChildren(pre); return hasNoChildren(pro); } //左右子树都非空 else { if(!pre->left && !pre->right || !pro->left && !pro->right) return abs(getHeight(pre)-getHeight(pro))<=1; q.push(pre->left); q.push(pre->right); q.push(pro->left); q.push(pro->right); } } return true; } };