No38：二叉树的深度

简单递归或者层次遍历

class Solution {
public:
	int maxDeep = 0;
	int curDeep = 0;
    void dfs(TreeNode* root){
		if(root == nullptr) return;
		curDeep++;
		maxDeep = max(curDeep, maxDeep);
		dfs(root->left);
		dfs(root->right);
		curDeep--;
		
	}

	int TreeDepth(TreeNode* pRoot) {
		dfs(pRoot);
		return maxDeep;
    }
};

层次遍历方法：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //空节点没有深度
        if(root == NULL) 
            return 0;
        //队列维护层次后续节点
        queue<TreeNode*> q; 
        //根入队
        q.push(root); 
        //记录深度
        int res = 0; 
        //层次遍历
        while(!q.empty()){ 
            //记录当前层有多少节点
            int n = q.size(); 
            //遍历完这一层，再进入下一层
            for(int i = 0; i < n; i++){ 
                TreeNode* node = q.front();
                q.pop();
                //添加下一层的左右节点
                if(node->left) 
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            //深度加1
            res++; 
        }
        return res;
    }
};

NO39：平衡二叉树

通过求左右子树的深度，判断当前节点是否为平衡二叉树； 同时还要递归求左右子节点是否也是平衡二叉树（因为可能有如下情况）：

    A
    / \
   B   C
  /     \
 D       E
/         \
F          G

下面这种算法的时间复杂度为On^2，空间复杂度为On

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

    bool IsBalanced_Solution(TreeNode* pRoot) {
        // write code here
        if(pRoot == nullptr) return true;
        // 分别求出左右子树最大深度
        int lHeight = dfs(pRoot->left);
        int rHeight = dfs(pRoot->right);
        if(abs(lHeight-rHeight) >= 2){
            return false;
        }
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
};

上述方法，实质上遍历了两轮二叉树，因此导致了On^2的时间复杂度。

时间复杂度为On的方法：根据定义，我们只需要后序遍历此树，从树的叶子节点开始计算高度，只要有一个子树不满足定义就返回-1，如果满足继续向上计算高度。

    int dfs(TreeNode* root){
        if(root == nullptr) return 0;
        int l = dfs(root->left);
        int r = dfs(root->right);
        if(l == -1 || r == -1 || abs(l-r) >= 2){
            return -1;
        }else{
            return max(l,r) + 1;
        }
    }

    bool IsBalanced_Solution(TreeNode* pRoot) {
        return dfs(pRoot) != -1;
    }