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语言代码。