[Golang][Leetcode][BinaryTree]刷題系列-106-Construct Binary Tree from Inorder and Postorder Traversal

Contents
106. Construct Binary Tree from Inorder and Postorder Traversal
Level : Medium
原題連結 : Click
題目 :
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example :
Note
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]
Example 2:
Input: inorder = [-1], postorder = [-1] Output: [-1]
解題思路 :
- 這個也是一個非常經典的題目! 題目給你兩組數組,分別是inorder排序與postorder排序,需要用兩個數組的特性去建構出linked node版本的binary tree
- inorder的特性是left -> mid -> right
- postorder的特性是 left -> right -> mid
- 由於以上兩種特性我可以做以下操作:
- 先取得postorder數組的最後一個element,他必定是mid(root)
- 再用該element去inorder中尋找,這樣就能依照inorder的規則去判斷左邊是Left tree 右邊是 right tree,將其與選出的root連接
- 重複以上動作
Recursive解法
- time complexity: O(n^2) , space complexity: O(n)
Runtime: 4 ms, faster than 90.98% of Go online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
|
|
最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!