# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
from typing import List
# 首先我們需要明白，二叉樹的前序遍歷，中序遍歷和后序遍歷分別是什么，
# 前序遍歷：根——左——右
# 中序遍歷：左——根——右
# 后序遍歷：左——右——根
# 因此我們可以看到這個案例
# 中序遍歷 inorder = [9,3,15,20,7]
# 后序遍歷 postorder = [9,15,7,20,3]
# 后序遍歷的根節點一定是在最后，那我們可以根據后序遍歷尋找到根節點，
# 然后根據根節點的值找到根節點在中序遍歷中的位置，在中序遍歷中根節點左邊的是
# 左子樹，右邊是右子樹，那么我們找到左右子樹的長度，
# 而在后序遍歷中，前邊是左子樹，中間是右子樹，最后是根節點，
# 那么我們可以根據左子樹和右子樹的長度來繼續進行遍歷，
# ps：這里我們所說的前提都是在二叉樹的所有節點都不重復的前提下，
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
return self.dfs(inorder,postorder)
def dfs(self,inorder,postorder):
# 這里如果串列為空，那么就回傳None，代表著已經到了葉子節點，
if inorder == []:
return None
# 找到根節點，
val = postorder[-1]
# 找到根節點在中序遍歷串列的位置
for i in range(len(inorder)):
if inorder[i] == val:
break
# 定義根節點，
root = TreeNode(val)
# 繼續向下遍歷，尋找左右子樹，
root.left = self.dfs(inorder[:i],postorder[:i])
root.right = self.dfs(inorder[i+1:],postorder[i:len(postorder) - 1])
# 最后回傳，
return root
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/125476.html
標籤：其他