LeetCode-105从前序与中序遍历序列构造二叉树(Construct Binary Tree from Preorder and Inorder Traversal)

LeetCode-105

Given preorder and inorder traversal of a tree, construct the binary tree.


Example

input:
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
return: [3,9,20,null,null,15,7]
   3
  /   \
9    20
     /    \
  15     7


Solution

Java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
int[] preorder;
int[] inorder;
int index=0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder=preorder;
this.inorder=inorder;
TreeNode root=building(0,inorder.length-1);
return root;
}
public TreeNode building(int left, int right) {
if (left>right)
return null;
TreeNode root=new TreeNode(preorder[index]);
index++;
root.left=building(left,normalSearch(inorder,root.val)-1);
root.right=building(normalSearch(inorder,root.val)+1,right);
return root;
}
public static int normalSearch(int array[],int e) {
for (int index=0;index<array.length;index++)
if (array[index]==e)
return index;
return -1;
}
}

题目描述:
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

总结:

执行用时11 ms,在所有 Java 提交中击败了84.82%的用户。
内存消耗37.8 MB,在所有 Java 提交中击败了65.49%的用户。

对递归还很不熟悉,对二叉树和图的操作也都很陌生,这道题的思路是参考Leetcode题解,后续会补充自己的算法和C语言代码。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×