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になる箇所を特定して、左なり右なりのノードに分けて、同じことを繰り返していきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
/** * 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); } } |
なんやねんこれまじで、辛いですね。それでは。
