[数据结构与算法]剑指offer55:二叉树的深度

emmm，算是基础了，简单来说就是求二叉树的深度，要用递归的思想来看。

比如对3，我们把他的左子树和右子树看成一团就好了，这两团的树高分别记作h1,h2，那么我们要怎么计算数高呢，当然是max(h1,h2)+1吧，然后用递归的思想，很容易写出来：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL) return 0;
        int left=maxDepth(root->left);
        int right=maxDepth(root->right);
        return left>right ? left+1 : right+1;
    }
};

结果是这样的：

?然后还有一道题：

?

?如果有求二叉搜索树的铺垫，很容易想出思路：对每一个节点，求出左右节点的高度，然后直接做差比较就好了。

代码如下：

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root==NULL) return true;
        return abs(height(root->left)-height(root->right))<=1 
        && isBalanced(root->left) && isBalanced(root->right);
    }

    int height(TreeNode* root)
    {
        if(root==NULL) return 0;
        return max(height(root->left),height(root->right))+1;    
    }
};

这也叫做自顶向下递归

但是细心的同学会发现，这样是不是多花了时间？没错，我们或许可以在求高度的过程中就完成对平衡树的判断，不是么，也就是自底向上递归，这样我们少花了一些时间。假设节点一共是n个，原来时间复杂度是O(n^2)，这里假设每个节点都要遍历一遍树就知道是O(n^2)了，如果自底向上就变成了O(n)，因为每个节点只要看一次。

代码如下所示：

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root==NULL) return true;
        return isBalancedCore(root)>0;
    }

    int isBalancedCore(TreeNode* root)
    {
        if(root==NULL) return 0;
        int left=isBalancedCore(root->left);
        int right=isBalancedCore(root->right);
        if(left==-1 || right==-1 || abs(left-right)>1)
        {
            return -1;
        }
        else
        {
            return max(left,right)+1;
        }
    }
};

结果如下所示：

一点心得：如果说自顶向下的调用是暴力调用高度函数的话，那么自底向上则是将高度函数做了细化处理，将左右子树的高度求出来的同时，也记录下当前节点的状态，若发现不是平衡的，返回-1（本题），若不是，则继续求高度。

其实这也可以类比动态规划中的一些自底向上自顶向下的优缺点好像~