剑指offer 面试55题

面试55题：

题目：二叉树的深度

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

解题思路：

①如果一棵树只有一个节点，它的深度为1

②如果根节点只有左子树而没有右子树，那么树的深度是左子树的深度加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 is None:

            return 0

        left = self.TreeDepth(pRoot.left)

        right = self.TreeDepth(pRoot.right)

        return max(left,right)+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):

        if pRoot is None:

            return 0

        left = self.TreeDepth(pRoot.left)

        right = self.TreeDepth(pRoot.right)

        return max(left,right)+1

    def IsBalanced_Solution(self, pRoot):

        # write code here

        if pRoot is None:

            return True

        left = self.TreeDepth(pRoot.left)

        right = self.TreeDepth(pRoot.right)

        diff = left - right

        if diff< -1 or diff >1:

            return False

        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)