LeetCode——Construct Binary Tree from Inorder and Postorder Traversal
1245 ワード
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
原題リンク:https://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
テーマ:1本の木の中序と後序を遍歴し、二叉樹を構築する.
解析:前の問題と同様に,後順遍歴の最後のノードをルートノードとし,このノードを中順遍歴で左右のサブツリーの境界とし,再帰的遍歴でノード間の依存関係を見つけることができる.
Note:
You may assume that duplicates do not exist in the tree.
原題リンク:https://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
テーマ:1本の木の中序と後序を遍歴し、二叉樹を構築する.
解析:前の問題と同様に,後順遍歴の最後のノードをルートノードとし,このノードを中順遍歴で左右のサブツリーの境界とし,再帰的遍歴でノード間の依存関係を見つけることができる.
public TreeNode buildTree(int[] inorder,int[] postorder) {
return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
}
public TreeNode buildTree(int[] inorder,int startin,int endin,int[] postorder,int startpost,int endpost){
if(startpost>endpost || startin>endin)
return null;
int pivot = postorder[endpost];
int index = 0;
for(;index<=endin;index++){
if(inorder[index]==pivot)
break;
}
TreeNode root = new TreeNode(pivot);
root.left = buildTree(inorder,startin,index-1,postorder,startpost,startpost+index-(startin+1));
root.right = buildTree(inorder,index+1,endin,postorder,startpost+index-startin,endpost-1);
return root;
}
// Definition for binary tree
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}