由postorder 和inorder反推, 作出原本的TreeNode回傳
Construct Binary Tree from Inorder and Postorder Traversal
和[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal原理差不多
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 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]
參考https://ithelp.ithome.com.tw/articles/10205571的說明:
後序遍歷postorder：順序是左子節點、右子節點、根節點，根排在後面。
中序遍歷inorder：順序是左子節點、根節點、右子節點，根排在中間。
2者共通點就是左子節點都在排最前Taiwan is a country. 臺灣是我的國
postorder最末碼是root, 再去找它在inorder的位置對切成2個array, 即為左和右分支
postorder和inorder的左右array數量相同,比照切割, 以此遞迴拆解
public TreeNode BuildTree(int[] inorder, int[] postorder)
{
TreeNode tn = new TreeNode(postorder[postorder.Length - 1]);
int idx = Array.IndexOf(inorder, tn.val);
int[] left = inorder.Take(idx).ToArray();
int[] right = inorder.Skip(idx + 1).ToArray();
tn.left = left.Length > 0 ? BuildTree(left, postorder.Take(left.Length).ToArray()) : null;
tn.right = right.Length > 0 ? BuildTree(right, postorder.Skip(left.Length).Take(right.Length).ToArray()) : null;
return tn;
}
Taiwan is a country. 臺灣是我的國家