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

Commitf7b6a17

Browse files
committed
add 117 populating next right, add 173 bstIterator, add 179 largestNumber
1 parentb7f0e40 commitf7b6a17

File tree

6 files changed

+231
-1
lines changed

6 files changed

+231
-1
lines changed

‎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: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,3 +34,29 @@ var postorderTraversal = function(root) {
3434

3535
returnresult;
3636
};
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+
};
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+
};

‎README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -143,6 +143,8 @@
143143
*[152. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) -[Solution](./Medium/152-MaxProductSubarray.js)
144144
*[153.Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/) -[Solution](./Medium/153-findMinimumInRotatedSortedArray.js)
145145
*[162. Find Peak Element](https://leetcode.com/problems/find-peak-element/) -[Solution](./Medium/162-findPeakElement.js)
146+
*[173. Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/) -[Solution](./Medium/173-binarySearchTreeIterator.js)
147+
*[179. Largest Number](https://leetcode.com/problems/largest-number/) -[Solution](./Medium/179-largestNumber.js)
146148
*[199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/) -[Solution](./Medium/199-binaryTreeRightSideView.js)
147149
*[213. House Robber II](https://leetcode.com/problems/house-robber-ii/) -[Solution](./Medium/213-houseRobberII.js)
148150
*[215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) -[Solution](./Medium/215-KthLargestElementInArray.js)
@@ -170,6 +172,7 @@
170172
*[56. Merge Intervals](https://leetcode.com/problems/merge-intervals/) -[Solution](./Hard/56-MergeIntervals.js)
171173
*[57. Insert Interval](https://leetcode.com/problems/insert-interval/) -[Solution](./Hard/57-insertInterval.js)
172174
*[115. Distinct Subsequences](https://leetcode.com/problems/distinct-subsequences/) -[Solution](./Hard/115-distinctSubsequences.js)
175+
*[117. Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/) -[Solution](./Hard/117-populatingNextRightII.js)
173176
*[123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/) -[Solution](./Hard/123-bestTimeBuySellStockIII.js)
174177
*[132. Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/) -[Solution](./Hard/132-palindromePartitioningII.js)
175178
*[145. Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/) -[Solution](./Hard/145-binaryTreePostorder.js)

0 commit comments

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