题解 | #平衡二叉树#

非递归方式判断平衡二叉树

class Solution {
public:
    bool hasNoChildren(TreeNode* node) {
        if (!node->left && !node->right)
            return true;
        return false;
    }
    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) {
                    if (!hasNoChildren(pre))
                        return false;
                }
                else {
                    if (!hasNoChildren(pro))
                        return false;
                }
            }
            //左右子树都非空
            else {
                q.push(pre->left);
                q.push(pre->right);
                q.push(pro->left);
                q.push(pro->right);
                //如果有一边子树全空，则需要交叉比较所有分支
                if (!pro->left && !pro->right||
                    !pre->left && !pre->right) {
                    q.push(pre->left);
                    q.push(pro->left);
                    q.push(pre->left);
                    q.push(pro->right);

                    q.push(pre->right);
                    q.push(pro->left);
                    q.push(pre->right);
                    q.push(pro->right);
                }
                //如果非全空，则只需要交叉比较不为空的分支
                else {
                    if (pre->left) {
                        if (pro->left) {
                            q.push(pre->left);
                            q.push(pro->left);
                        }
                        if (pro->right) {
                            q.push(pre->left);
                            q.push(pro->right);
                        }
                    }

                    if (pre->right) {
                        if (pro->left) {
                            q.push(pre->right);
                            q.push(pro->left);
                        }
                        if (pro->right) {
                            q.push(pre->right);
                            q.push(pro->right);
                        }
                    }
                }
            }
        }
        return true;
    }
};