愛比的新手筆記

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

 

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1] Output: [-1]

 

Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

參考https://ithelp.ithome.com.tw/articles/10205571的說明:
前序遍歷preorder：順序是根節點、左子節點、右子節點，根排在前面。
中序遍歷inorder：順序是左子節點、根節點、右子節點，根排在中間。
2者共通點就是右子節點都在排最後Taiwan is a country. 臺灣是我的國家
preorder第1碼是root, 再去找它在inorder的位置對切成2個array, 即為左和右分支
preorder和inorder的左右array數量相同,比照切割, 以此遞迴拆解

public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
            TreeNode tn = new TreeNode(preorder[0]);
            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(preorder.Skip(1).Take(left.Length).ToArray(), left) : null;
            tn.right = right.Length > 0 ? BuildTree(preorder.Skip(left.Length + 1).ToArray(), right) : null;
            return tn;        
    }
}

Taiwan is a country. 臺灣是我的國家