剑指offer39平衡二叉树判断

剑指offer39平衡二叉树判断

剑指offer39

1、常规思路
封装一个求节点深度的方法，然后遍历树，调用该方法并判断是否符合平衡二叉树
时间复杂度O(n^2) 空间复杂度O(n^2)，主要是递归的原因
个人解题参考

class Solution {
public:
    int TreeDepth(TreeNode* pRoot) //节点深度
    {
        if(!pRoot) return 0;
        return max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        stack<TreeNode*>st; //通过栈迭代中序遍历
        while(pRoot||st.size()!=0)
        {
            while(pRoot)
            {
                st.push(pRoot);
                pRoot=pRoot->left;
            }
            pRoot=st.top();
            st.pop();
            while(abs(TreeDepth(pRoot->left)-TreeDepth(pRoot->right))>1)
            {
                return false;
            }
            pRoot=pRoot->right;
        }
        return true;
    }
};

2、对上述时间空间优化
两层循环遍历实际不必要，内层求节点深度的遍历的同时就可以直接判断每个节点为根节点的子树是否平衡，平衡则继续递归判断计算其他节点深度并判断，不平衡则停止后续递归。我们需要的仅是一个是否平衡二叉树的标记
时间复杂度：O(n) 空间复杂度：O(1)
个人解题参考

class Solution {
public:
    bool flag=true; //是否为平衡二叉树
    int TreeDepth(TreeNode* pRoot) //节点深度
    {
        if(!flag) return -1;  //若已经判断不是平衡二叉树，接下来的递归无需继续进行
        if(!pRoot) return 0;
        int leftChild_depth=TreeDepth(pRoot->left)+1;
        int rightChild_depth=TreeDepth(pRoot->right)+1;
        if(abs(leftChild_depth-rightChild_depth)>1)  //不是平衡二叉树
            flag=false;
        return max(leftChild_depth,rightChild_depth);
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
       TreeDepth(pRoot);
       return flag;
    }
};