面试题55：二叉树的深度

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

思路：
这道题目只需要计算出树的深度而无需记录节点，根据题意，如果当前节点只有左子树，那么深度为左子树加1；如果当前节点只有右子树，那么深度为右子树加1；如果两个子树都有，那么树的深度是左右子树中深度较大的加1。以上代码可以利用递归比较简单的实现。

代码实现：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot == None:
            return 0      #递归结束条件
        nleft = self.TreeDepth(pRoot.left)
        nright = self.TreeDepth(pRoot.right)
        if nleft>nright:
            return nleft+1
        else:
            return nright+1

提交结果：

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

思路：
这道题可以利用上述的思路，每次进行遍历左右子树，然后得出其深度，然后再计算是否平衡。但是这种算法自顶而下，会有重复，因此我们想寻求优化的方法，可以采用后序遍历，每次遍历时顺便将深度保存然后计算出是否平衡，如果不平衡会返回对应标志，直至结束为止，这样可以避免重复而解决问题。

代码实现：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here\
        return self.HeightCore(pRoot)>=0
    

    #后续遍历的思想
    def HeightCore(self,pRoot):
        if not pRoot:
            return 0   #深度为0
        nleft = self.HeightCore(pRoot.left)
        nright = self.HeightCore(pRoot.right)
        if abs(nleft-nright)<=1 and nleft>=0 and nright>=0:  #每次对遍历的左子树和右子树深度进行判断
            return max(nleft,nright)+1
        else:
            return -1   #否则不平衡

提交结果：