二叉树的深度（平衡二叉树）

题目

　　输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

思路

　　如果一棵树只有一个结点，它的深度为1，如果根节点只有左子树而没有右子树，那么树的深度应该是其左子树的深度+1.同样如果根节点只有右子树而没有左子树，那么树的深度应该是其右子树+1.如果既有左子树又有右子树，那概述的深度就是左、右子树的深度的较大值加1。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* root)
    {
        if(!root)
            return 0;
        int leftDepth=TreeDepth(root->left);
        int rightDepth=TreeDepth(root->right);
        
        return max(leftDepth,rightDepth)+1;
    }
};

题目

　　输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路

　　如果像去求二叉树的深度那样，先判断根节点是不是平衡的，在判断根的左右子树是不是平衡的，这样的话，会重复遍历很多节点（根的左右子树的子树），所以可以用后序遍历，遍历到根结点之前已经先遍历了左右子树，只需要在便利每个结点的时候记录它的深度，就可以一遍遍历一边判断每个节点是不是平衡的。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* root) {
        if(!root)
            return true;
        
        return IsBalanced_Solution_Core(root,0);
    }
private:
    bool IsBalanced_Solution_Core(TreeNode *root,int n)
    {
        if(!root)
        {
            n=0;
            return true;
        }
        int left=0,right=0;
        if(IsBalanced_Solution_Core(root->left,left)&&IsBalanced_Solution_Core(root->right,right))
        {
            int diff=left-right;
            if(abs(diff)<=1)
            {
                n=max(left,right)+1;
                return true;
            }
        }
        return false;
    }
};