leetcode-105-114

leetcode105题114题:

leetcode105题(从前序和中序遍历序列构造二叉树):

根据一棵树的前序遍历与中序遍历构造二叉树。

示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var buildTree = function(preorder, inorder) {
var tree = reConstructBinaryTree1(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
return tree;
};
function reConstructBinaryTree1(pre,prestart,preend,vin,vinstart,vinend){
if(prestart>preend||vinstart>vinend){
return null;
}
var tree = new TreeNode(pre[prestart]);
for(var i=0;i<vin.length;i++){
if(pre[prestart]===vin[i]){
tree.left = reConstructBinaryTree1(pre,prestart+1,prestart+i-vinstart,vin,vinstart,i-1);
tree.right = reConstructBinaryTree1(pre,prestart+i-vinstart+1,preend,vin,i+1,vinend);
}
}
return tree;
}

leetcode114题(二叉树展开为链表):

给定一个二叉树,原地将它展开为链表。

示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function LinkNode(val){
this.val = val;
this.next = null;
}
var flatten = function(root) {
var head = new LinkNode(null);//建立链表的头结点
var temp = head;
var arr = [];//用来存放深度优先遍历的结果
function flatten1(arr,root){
if(root==null){
return;
}
arr.push(root.val);
flatten1(arr,root.left);
flatten1(arr,root.right);
}
flatten1(arr,root);
for(var i=0;i<arr.length;i++){
var node = new LinkNode(arr[i]);
temp.next = node;
temp = temp.next;
}
return head.next;
};
分享到