本文首發(fā)于我的個(gè)人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/03/target-offer-reconstruct-binary-tree.html 作者: Suixin
題目描述
輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果绘闷，請(qǐng)重建出該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字乳规。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹(shù)并返回担敌。
解題思路
前序遍歷：NLR
中序遍歷：LNR
對(duì)于前序遍歷的結(jié)果崎淳，若為空柜与，則二叉樹(shù)為空，若長(zhǎng)度為1悄蕾，則二叉樹(shù)只有一個(gè)結(jié)點(diǎn)即為根結(jié)點(diǎn)票顾。第一個(gè)元素一定為二叉樹(shù)的根結(jié)點(diǎn)。對(duì)于中序遍歷的結(jié)果帆调，根結(jié)點(diǎn)所處的位置前面的為左子樹(shù)的中序遍歷結(jié)果奠骄，右面的為右子樹(shù)的中序遍歷結(jié)果。分別可以得到左子樹(shù)和右子樹(shù)的結(jié)點(diǎn)數(shù)量番刊，在前序遍歷中數(shù)數(shù)即可分開(kāi)左右子樹(shù)的前序遍歷結(jié)果含鳞。通過(guò)遞歸可重建二叉樹(shù)。
例子：
前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}芹务。
分析步驟：
- 根結(jié)點(diǎn)為1蝉绷，則左子樹(shù)的中序遍歷結(jié)果為{4,7,2}，右子樹(shù)的中序遍歷結(jié)果為{5,3,8,6}枣抱；
- 左子樹(shù)共有3個(gè)結(jié)點(diǎn)熔吗，則左子樹(shù)的前序遍歷結(jié)果為{2,4,7}，右子樹(shù)的前序遍歷結(jié)果為{3,5,6,8}佳晶；
- 遞歸分別對(duì)左子樹(shù)和右子樹(shù)重建二叉樹(shù)磁滚。
代碼
Python(2.7.3)
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回構(gòu)造的TreeNode根節(jié)點(diǎn)
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre) == 0:
return None
elif len(pre) == 1:
return TreeNode(pre[0])
else:
root = TreeNode(pre[0])
root.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0]) + 1], tin[:tin.index(pre[0])])
root.right = self.reConstructBinaryTree(pre[tin.index(pre[0]) + 1:], tin[tin.index(pre[0]) + 1:])
return root
運(yùn)行時(shí)間：43ms
占用內(nèi)存：5860k
參考
https://www.nowcoder.com/profile/1954887/codeBookDetail?submissionId=9260715
