[Leetcode] 0105. 先行順序と中順序の走査から二分木を構築する

/ リートコード, テクニカル記事 / による

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリ リンク

2つの整数配列が与えられる 予約注文 そして 順番に どこ 予約注文 二分木の前順序走査であり、 順番に 同じツリーのインオーダートラバーサルを構築して返す バイナリツリー.

 

例 1:

入力： 先行順序 = [3,9,20,15,7]、先行順序 = [9,3,15,20,7]
出力： [3,9,20,null,null,15,7]

例 2:

入力： 先行順序 = [-1]、インオーダー = [-1]
出力： [-1]

 

制約:

  • 1 <= 事前注文の長さ <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i]、inorder[i] <= 3000
  • 予約注文 そして 順番に 構成する 個性的 価値観。
  • 各値は 順番に 以下にも登場 予約注文.
  • 予約注文 は 保証された ツリーの事前順序走査になります。
  • 順番に は 保証された ツリーの内順走査になります。
 

パイソン

				
					# 時間計算量: O(n) # 空間計算量: O(n) from entering List, Optional class ソリューション: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: def dfs(left: int, right: int): nonlocal preorderIndex if left > right: return None rootValue = preorder[preorderIndex] root = TreeNode(rootValue) preorderIndex += 1 root.left = dfs(left, inorderMap[rootValue] - 1) root.right = dfs(inorderMap[rootValue] + 1, right) return root preorderIndex = 0 inorderMap = {} for i, value in enumerate(inorder): inorderMap[value] = i return dfs(0, len(inorder) - 1) preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7] print(Solution().buildTree(preorder, inorder))

関連記事

ja日本語
zh_TW繁體中文 en_USEnglish zh_CN简体中文 ko_KR한국어 es_ESEspañol ja日本語