[Leetcodeやるお]105.Construct Binary Tree from Inorder and Postorder Traversal

Leetcodeの学習メモです。みんな大好きBinary Tree！

Input:
inorder = [9,3,15,20,7],
postorder = [9,15,7,20,3]

があって、Binary Treeを構築しなさいよ、という問題です。
inorderはLeft-> Node -> Rightという順番、postorderはLeft->Right->Nodeという順番です。（いっつも忘れるけども）

最終目標となる、Outputは [3,9,20,null,null,15,7]です。

アプローチ

PostOrderの最後には必ずrootが入るので利用できます。
postorder = [9,15,7,20,3]がrootになります。

ここでinorderをみます

inorder = [9,3,15,20,7],

inorderの中で3（root）より前に存在するものが、rootの左側のnodeということになります。この場合だと9がrootに対して左のnodeになります。

inorder = [9,3,15,20,7],
inorderでは左にあるものの数が小さくなります。

inorder = [9,3,15,20,7],
postorder = [9,15,7,20,3]

ここで、9がrootに対して左にある単一のnodeだとわかりました。問題は

inorder = [9,3,15,20,7],
postorder = [9,15,7,20,3]

青のサブノードの部分ですね。

inorder = [15,20,7],
postorder = [15,7,20]

同じようにpostorderの末尾を見ると20がrootであることがわかります。そこでinorderから20を探し、15が左のnode,7が右のnodeであることがわかります。

これを利用して再帰的なfunctionを利用してBinary Treeを構築していきます。
Nodeになる箇所を特定して、左なり右なりのノードに分けて、同じことを繰り返していきます。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode buildTree_rec(int[] inorder, int i1, int i2, int[] postorder, int p1, int p2){
        if(i1 >= i2 || p1 >= p2 ) return null;
        TreeNode root = new TreeNode(postorder[p2-1]);
        int it = 0;
        for(int i = i1; i < i2; i++){
            if(postorder[p2-1] == inorder[i]){
                it = i;
                break;
            }
        }
        int diff = it - i1;
        root.left = buildTree_rec(inorder , i1, i1 + diff , postorder, p1, p1+ diff);
        root.right = buildTree_rec(inorder , i1 + diff + 1, i2 , postorder, p1+diff, p2-1);
        
        return root;
        
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        if(n == 0) return null;
        return buildTree_rec(inorder, 0 , n , postorder , 0, n);
    }
}

なんやねんこれまじで、辛いですね。それでは。