Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit957122c

Browse files
committed
2 parentsf198219 +f7b6a17 commit957122c

12 files changed

+376
-3
lines changed

‎Easy/102-binaryTreeLevelOrder.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -72,7 +72,7 @@ var levelOrder = function(root) {
7272

7373
varhelper=function(results,node,level){
7474
if(!node)returnresults;
75-
if(level>=results.length){
75+
if(level===results.length){
7676
results[level]=[];
7777
}
7878
results[level].push(node.val);

‎Hard/117-populatingNextRightII.js‎

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
/**
2+
* Definition for binary tree with next pointer.
3+
* function TreeLinkNode(val) {
4+
* this.val = val;
5+
* this.left = this.right = this.next = null;
6+
* }
7+
*/
8+
9+
/**
10+
*@param {TreeLinkNode} root
11+
*@return {void} Do not return anything, modify tree in-place instead.
12+
*/
13+
// BFS, level order Traversal, set a dummy head at the beginnig of each level.
14+
// Is it O(1) space?
15+
varconnect=function(root){
16+
while(root){
17+
varleftDummy=newTreeLinkNode(0);
18+
varcurrChild=leftDummy;
19+
while(root){
20+
if(root.left){
21+
currChild.next=root.left;
22+
currChild=currChild.next;
23+
}
24+
if(root.right){
25+
currChild.next=root.right;
26+
currChild=currChild.next;
27+
}
28+
root=root.next;
29+
}
30+
// reset head to the left of each level.
31+
root=leftDummy.next;
32+
}
33+
};
34+
35+
36+
/**
37+
* Definition for binary tree with next pointer.
38+
* function TreeLinkNode(val) {
39+
* this.val = val;
40+
* this.left = this.right = this.next = null;
41+
* }
42+
*/
43+
44+
// BFS too, but constant space
45+
varconnect=function(root){
46+
// next level's head (beginnig)
47+
varhead=root;
48+
// next level's last visited node
49+
varprev;
50+
// curr level's currently visiting node
51+
varcurr;
52+
while(head){
53+
curr=head;
54+
prev=null;
55+
head=null;
56+
while(curr){
57+
if(curr.left){
58+
if(prev)prev.next=curr.left;
59+
elsehead=curr.left;
60+
prev=curr.left;
61+
}
62+
if(curr.right){
63+
if(prev)prev.next=curr.right;
64+
elsehead=curr.right;
65+
prev=curr.right;
66+
}
67+
curr=curr.next;
68+
}
69+
}
70+
};
71+
72+
// doesn't work, wrong answer. e.g. {1,2,3,4,5,#,6,7,#,#,#,#,8},
73+
// the common parent is one more level up
74+
varconnect=function(root){
75+
if(!root)return;
76+
77+
while(root){
78+
varpNode=root;
79+
while(pNode){
80+
varchild=null;
81+
if(pNode.left&&pNode.right){
82+
pNode.left.next=pNode.right;
83+
child=pNode.right;
84+
}else{
85+
if(pNode.left)child=pNode.left;
86+
if(pNode.right)child=pNode.right;
87+
}
88+
if(child){
89+
if(pNode.next){
90+
if(pNode.next.left)child.next=pNode.next.left;
91+
elsechild.next=pNode.next.right;
92+
}
93+
}
94+
pNode=pNode.next;
95+
}
96+
97+
while(root&&!root.left&&!root.right){
98+
root=root.next;
99+
}
100+
if(!root)break;
101+
if(root.left)root=root.left;
102+
elseif(root.right)root=root.right;
103+
}
104+
};

‎Hard/145-binaryTreePostorder.js‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* function TreeNode(val) {
4+
* this.val = val;
5+
* this.left = this.right = null;
6+
* }
7+
*/
8+
/**
9+
*@param {TreeNode} root
10+
*@return {number[]}
11+
*/
12+
// looks like there is a better way to implement
13+
varpostorderTraversal=function(root){
14+
varresult=[];
15+
if(!root)returnresult;
16+
varstack=[root];
17+
varpreVisitedNode=null;
18+
19+
while(stack.length>0){
20+
node=stack[stack.length-1];
21+
if(!node.left&&!node.right||
22+
(preVisitedNode&&(preVisitedNode===node.right||preVisitedNode===node.left))){
23+
result.push(node.val);
24+
preVisitedNode=stack.pop();
25+
}else{
26+
if(node.right){
27+
stack.push(node.right);
28+
}
29+
if(node.left){
30+
stack.push(node.left);
31+
}
32+
}
33+
}
34+
35+
returnresult;
36+
};
37+
38+
// an improved version
39+
varpostorderTraversal=function(root){
40+
varresult=[];
41+
if(!root)returnresult;
42+
varstack=[root];
43+
44+
while(stack.length>0){
45+
varnode=stack[stack.length-1];
46+
if(!node.left&&!node.right){
47+
result.push(node.val);
48+
node=stack.pop();
49+
}else{
50+
if(node.right){
51+
stack.push(node.right);
52+
node.right=null;
53+
}
54+
if(node.left){
55+
stack.push(node.left);
56+
node.left=null;
57+
}
58+
}
59+
}
60+
61+
returnresult;
62+
};

‎Medium/116-PopulatingNextRightPointersinEachNode.js‎

Lines changed: 22 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
/**
1010
* Key: if a node is a parent's left child, then this node's next is its parent's right child node.
1111
* if a node is a parent node's right child, then this node's next is its parent's next node's left node.
12-
* (the parent node should have next child). The trick part is how to write code.
12+
* (the parent node should have next child). The trick part is how to write code.
1313
*
1414
*@param {TreeLinkNode} root
1515
*@return {void} Do not return anything, modify tree in-place instead.
@@ -27,3 +27,24 @@ var connect = function(root) {
2727
root=root.left;
2828
}
2929
};
30+
31+
// second try, slow, but easy understanding
32+
// the space is not constant
33+
varconnect=function(root){
34+
if(!root)return;
35+
root.next=null;
36+
varqueue=[root];
37+
while(queue.length>0){
38+
varnode=queue.shift();
39+
if(node.left){
40+
node.left.next=node.right;
41+
queue.push(node.left);
42+
}
43+
if(node.right){
44+
if(node.next){
45+
node.right.next=node.next.left;
46+
}
47+
queue.push(node.right);
48+
}
49+
}
50+
};

‎Medium/139-wordBreak.js‎

Lines changed: 17 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
*@return {boolean}
77
*/
88

9-
// recursion, not accepted, time exceeds limits.
9+
// recursion, not accepted, time exceeds limits. O(N^2)
1010
varwordBreak=function(s,wordDict){
1111
returnhelper(s,wordDict,0);
1212
};
@@ -22,3 +22,19 @@ var helper = function(s, wordDict, start) {
2222
}
2323
returnfalse;
2424
};
25+
26+
// Dynamic, accepted
27+
varwordBreak=function(s,wordDict){
28+
varcanBreak=[true];
29+
for(vari=0;i<s.length;i++){
30+
if(!canBreak[i])continue;
31+
for(varwordofwordDict){
32+
varwLength=word.length;
33+
if(canBreak[i+wLength])continue;
34+
if(s.substring(i,i+wLength)===word){
35+
canBreak[i+wLength]=true;
36+
}
37+
}
38+
}
39+
returncanBreak[s.length] ?true :false;
40+
};

‎Medium/144-binaryTreePreorder.js‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,3 +24,24 @@ var preorderTraversal = function(root) {
2424
}
2525
returnorder;
2626
};
27+
28+
// this is a more straightforward method, but slower than first one.
29+
// stack tracks the node visit order
30+
varpreorderTraversal=function(root){
31+
if(!root)return[];
32+
varresult=[];
33+
varstack=[root];
34+
35+
while(stack.length>0){
36+
varnode=stack.pop();
37+
result.push(node.val);
38+
if(node.right){
39+
stack.push(node.right);
40+
}
41+
if(node.left){
42+
stack.push(node.left);
43+
}
44+
}
45+
46+
returnresult;
47+
};
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/**
2+
* Definition for binary tree
3+
* function TreeNode(val) {
4+
* this.val = val;
5+
* this.left = this.right = null;
6+
* }
7+
*/
8+
9+
/**
10+
*@constructor
11+
*@param {TreeNode} root - root of the binary search tree
12+
*/
13+
// Is there a better solution?
14+
varBSTIterator=function(root){
15+
this.stack=[];
16+
this.pushStack(root);
17+
};
18+
19+
/**
20+
*@this BSTIterator
21+
*@returns {boolean} - whether we have a next smallest number
22+
*/
23+
BSTIterator.prototype.hasNext=function(){
24+
returnthis.stack.length>0 ?true :false;
25+
};
26+
27+
/**
28+
*@this BSTIterator
29+
*@returns {number} - the next smallest number
30+
*/
31+
BSTIterator.prototype.next=function(){
32+
varsmall=this.stack.pop();
33+
if(small.right){
34+
this.pushStack(small.right);
35+
}
36+
returnsmall.val;
37+
};
38+
39+
BSTIterator.prototype.pushStack=function(node){
40+
while(node){
41+
this.stack.push(node);
42+
node=node.left;
43+
}
44+
};
45+
46+
/**
47+
* Your BSTIterator will be called like this:
48+
* var i = new BSTIterator(root), a = [];
49+
* while (i.hasNext()) a.push(i.next());
50+
*/

‎Medium/179-largestNumber.js‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
/**
2+
*@param {number[]} nums
3+
*@return {string}
4+
*/
5+
varlargestNumber=function(nums){
6+
nums.sort(function(a,b){
7+
varab=a+''+b;
8+
varba=b+''+a;
9+
if(ab<ba)return1;
10+
elseif(ab>ba)return-1;
11+
return0;
12+
});
13+
if(nums[0]===0)return'0';
14+
returnnums.join('');
15+
};
16+
17+
// this is a wrong solution e.g. [121,12] '12' < '121', then it doesn't work.
18+
varlargestNumber=function(nums){
19+
nums.sort(function(a,b){
20+
if(a.toString()<b.toString())return1;
21+
elseif(a.toString()>b.toString())return-1;
22+
elsereturn0;
23+
});
24+
if(nums[0]===0)return'0';
25+
returnnums.join('');
26+
};

‎Medium/230-kthSmallestElementinBST.js‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,3 +29,21 @@ var kthSmallest = function(root, k) {
2929
}
3030
}
3131
};
32+
33+
// second try
34+
varkthSmallest=function(root,k){
35+
varstack=[];
36+
37+
while(root||stack.length>0){
38+
while(root){
39+
stack.push(root);
40+
root=root.left;
41+
}
42+
root=stack.pop();
43+
k--;
44+
if(k===0)returnroot.val;
45+
root=root.right;
46+
}
47+
48+
return0;
49+
};

‎Medium/60-permutationSequence.js‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/**
2+
*@see inline comments
3+
*
4+
*@param {number} n
5+
*@param {number} k
6+
*@return {string}
7+
*/
8+
vargetPermutation=function(n,k){
9+
varnums=[];
10+
for(vari=0;i<n;i++){
11+
nums.push(i+1);
12+
}
13+
k--;
14+
varmod=1;
15+
for(i=1;i<n;i++){
16+
mod*=i;
17+
}
18+
varresult='';
19+
for(i=0;i<n;i++){
20+
// find the index of current number's first digit
21+
varindex=Math.floor(k/mod);
22+
k=k%mod;
23+
result+=nums[index];
24+
// remove this used number from nums.
25+
nums.splice(index,1);
26+
mod=Math.floor(mod/(n-i-1));
27+
}
28+
29+
returnresult;
30+
};

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp