剑指Offer数据结构之树[Python版]

面试题004 重建二叉树

题目表述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路：
递归思想。前序遍历中第一个元素是根，因此在中序遍历中找到根的位置下标，根将中序遍历分为两部分，分别是左子树和右子树，然后继续递归寻找左右子树的根节点。
代码：

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre or not tin:
            return None
        root = TreeNode(pre[0])
        index = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:1+index],tin[:index])
        root.right = self.reConstructBinaryTree(pre[1+index:],tin[1+index:])
        return root

面试题038 二叉树的深度

题目描述：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
解题思路：一棵二叉树的深度是其左子树和右子树深度的最大值+1。拿左子树的深度来讲，左子树的深度等于其左右子树深度的最大值+1。递归这一过程即可
求树的深度，可以从层次遍历出发考虑,层次遍历可以使用队列完成，也可以使用递归完成
代码

方法一：使用队列
class Solution:
????# 层次遍历
????def levelOrder(self, root):
??? ? ??# write your code here
??? ? ??# 存储最后层次遍历的结果
??? ? ??res?= []
??? ? ??# 层数
??? ? ??count?= 0
??? ? ??# 如果根节点为空，则返回空列表
??? ? ??if root?is None:
??? ? ? ? ??return count
??? ? ??# 模拟一个队列储存节点
??? ? ??q?= []
??? ? ??# 首先将根节点入队
??? ? ??q.append(root)
??? ? ??# 列表为空时，循环终止
??? ? ??while len(q) != 0:
??? ? ? ? ??# 使用列表存储同层节点
??? ? ? ? ??tmp?= []
??? ? ? ? ??# 记录同层节点的个数
??? ? ? ? ??length?= len(q)
??? ? ? ? ??for i?in range(length):
??? ? ? ? ? ? ??# 将同层节点依次出队
??? ? ? ? ? ? ??r?= q.pop(0)
??? ? ? ? ? ? ??if r.left?is not None:
??? ? ? ? ? ? ? ? ??# 非空左孩子入队
??? ? ? ? ? ? ? ? ??q.append(r.left)
??? ? ? ? ? ? ??if r.right?is not None:
??? ? ? ? ? ? ? ? ??# 非空右孩子入队
??? ? ? ? ? ? ? ? ??q.append(r.right)
??? ? ? ? ? ? ??tmp.append(r.val)
??? ? ? ? ??if tmp:
??? ? ? ? ? ? ??count?+= 1? # 统计层数
??? ? ? ? ??res.append(tmp)
??? ? ??return count
?
????def TreeDepth(self, pRoot):
??? ? ??# write code here
??? ? ??# 使用层次遍历
??? ? ??# 当树为空直接返回0
??? ? ??if pRoot?is None:
??? ? ? ? ??return 0
??? ? ??count?= self.levelOrder(pRoot)
??? ? ??return count
?
方法二：使用递归方法
class Solution:
????def TreeDepth(self, pRoot):
??? ? ??# write code here
??? ? ??# 使用层次遍历
??? ? ??# 当树为空直接返回0
??? ? ??if pRoot?is None:
??? ? ? ? ??return 0
??? ? ??# 方法2：使用递归
??? ? ??# 如果该树只有一个结点，它的深度为1.如果根节点只有左子树没有右子树，
??? ? ??# 那么树的深度为左子树的深度加1；同样，如果只有右子树没有左子树，
??? ? ??# 那么树的深度为右子树的深度加1。如果既有左子树也有右子树，
??? ? ??# 那该树的深度就是左子树和右子树的最大值加1.
??? ? ??count?= max(self.TreeDepth(pRoot.left),?self.TreeDepth(pRoot.right))?+ 1
??? ? ??return count

面试题039 平衡二叉树

题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
一棵高度平衡二叉树定义：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
解题思路：
方法一：自顶向下,对于每个节点，都计算一下左子树以及右子树的差的绝对值，即每个节点都判断一下。
算法复杂度为O（N*2）
代码

class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:
            return True
        left = self.depth(pRoot.left)
        right = self.depth(pRoot.right)
        return abs(left - right) <= 1 and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
    def depth(self, pRoot):
        if not pRoot:
            return 0
        return 1 + max(self.depth(pRoot.left), self.depth(pRoot.right))

方法二：自下往上 算法复杂度O(N)
代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#???? def __init__(self, x):
#???????? self.val = x
#???????? self.left = None
#???????? self.right = None
class Solution:
????def IsBalanced_Solution(self, p):
????????return self.dfs(p) != -1
????def dfs(self, p):
????????if p is None:
????????????return 0
????????left = self.dfs(p.left)
????????if left == -1:
????????????return -1
????????right = self.dfs(p.right)
????????if right == -1:
????????????return -1
????????if abs(left - right) > 1:
????????????return -1
????????return max(left, right) + 1