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

Commitdf1c68a

Browse files
committed
continue tree problems: 107,103
1 parentd3adb6a commitdf1c68a

File tree

5 files changed

+134
-6
lines changed

5 files changed

+134
-6
lines changed

‎Easy/101-symmetricTree.js‎

Lines changed: 39 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@ var isSymmetric = function(root) {
1818
varisSymmetricHelper=function(left,right){
1919
if(!left||!right)returnleft===right;
2020
if(left.val!==right.val)returnfalse;
21-
elsereturnisSymmetricHelper(left.left,right.right)&&isSymmetricHelper(left.right,right.left);
21+
returnisSymmetricHelper(left.left,right.right)&&isSymmetricHelper(left.right,right.left);
2222
};
2323

2424
// iterative
@@ -29,7 +29,9 @@ var isSymmetric = function(root) {
2929
if(!root.right)returnfalse;
3030
treeStack.push(root.left);
3131
treeStack.push(root.right);
32-
}elseif(root.right)returnfalse;
32+
}elseif(root.right){
33+
returnfalse;
34+
}
3335

3436
while(treeStack.length>0){
3537
if(treeStack.length%2!==0)returnfalse;
@@ -38,16 +40,47 @@ var isSymmetric = function(root) {
3840
if(right.val!==left.val)returnfalse;
3941
if(left.left){
4042
if(!right.right)returnfalse;
41-
treeStack.push(left.left);
42-
treeStack.push(right.right);
43+
treeStack.push(left.left,right.right);
4344
}elseif(right.right)returnfalse;
4445

4546
if(right.left){
4647
if(!left.right)returnfalse;
47-
treeStack.push(right.left);
48-
treeStack.push(left.right);
48+
treeStack.push(right.left,left.right);
4949
}elseif(left.right)returnfalse;
5050
}
5151

5252
returntrue;
5353
};
54+
55+
// a second try
56+
varisSymmetric=function(root){
57+
if(!root)returntrue;
58+
varstack=[];
59+
if(root.left&&root.right){
60+
stack.push(root.left);
61+
stack.push(root.right);
62+
}elseif(!root.left&&!root.right){
63+
returntrue;
64+
}else{
65+
returnfalse;
66+
}
67+
68+
while(stack.length>0){
69+
if(stack.length%2!==0)returnfalse;
70+
varleft=stack.pop();
71+
varright=stack.pop();
72+
if(left.val!==right.val)returnfalse;
73+
if(left.left&&right.right){
74+
stack.push(left.left,right.right);
75+
}elseif((!left.left&&right.right)||(left.left&&!right.right)){
76+
returnfalse;
77+
}
78+
if(right.left&&left.right){
79+
stack.push(right.left,left.right);
80+
}elseif((!right.left&&left.right)||(right.left&&!left.right)){
81+
returnfalse;
82+
}
83+
}
84+
85+
returntrue;
86+
};

‎Easy/102-binaryTreeLevelOrder.js‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,3 +34,48 @@ var levelOrder = function(root) {
3434

3535
returnresult;
3636
};
37+
38+
// second try
39+
varlevelOrder=function(root){
40+
varresults=[];
41+
if(!root)returnresults;
42+
varprevLevel=[root];
43+
varcurrLevel=[];
44+
varresult=[];
45+
46+
while(prevLevel.length>0){
47+
while(prevLevel.length>0){
48+
varnode=prevLevel.shift();
49+
result.push(node.val);
50+
if(node.left){
51+
currLevel.push(node.left);
52+
}
53+
if(node.right){
54+
currLevel.push(node.right);
55+
}
56+
}
57+
results.push(result);
58+
prevLevel=currLevel;
59+
currLevel=[];
60+
result=[];
61+
}
62+
63+
returnresults;
64+
};
65+
66+
// third try, recursive. DFS.
67+
varlevelOrder=function(root){
68+
varresults=[];
69+
helper(results,root,0);
70+
returnresults;
71+
};
72+
73+
varhelper=function(results,node,level){
74+
if(!node)returnresults;
75+
if(level>=results.length){
76+
results[level]=[];
77+
}
78+
results[level].push(node.val);
79+
helper(results,node.left,level+1);
80+
helper(results,node.right,level+1);
81+
};
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
/**
2+
*@param {TreeNode} root
3+
*@return {number[][]}
4+
*/
5+
varlevelOrderBottom=function(root){
6+
varresults=[];
7+
helper(root,0,results);
8+
returnresults;
9+
};
10+
11+
varhelper=function(node,level,results){
12+
if(!node)returnresults;
13+
if(level>=results.length){
14+
// insert level result array reversely
15+
results.unshift([]);
16+
}
17+
results[results.length-level-1].push(node.val);
18+
helper(node.left,level+1,results);
19+
helper(node.right,level+1,results);
20+
};
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/**
2+
* Key: same idea as binary tree level order traversal,
3+
* if the level is odd, insert the node to the begining of the level result array
4+
* if the level is even, insert the node to the end of the level result array
5+
*
6+
*@param {TreeNode} root
7+
*@return {number[][]}
8+
*/
9+
varzigzagLevelOrder=function(root){
10+
varresults=[];
11+
helper(results,root,0);
12+
returnresults;
13+
};
14+
15+
varhelper=function(results,node,level){
16+
if(!node)returnresults;
17+
if(level>=results.length){
18+
results[level]=[];
19+
}
20+
if(level%2===0){
21+
results[level].push(node.val);
22+
}else{
23+
results[level].unshift(node.val);
24+
}
25+
26+
helper(results,node.left,level+1);
27+
helper(results,node.right,level+1);
28+
};

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@
2727
*[101. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/) -[Solution](./Easy/101-symmetricTree.js)
2828
*[102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/) -[Solution](./Easy/102-binaryTreeLevelOrder.js)
2929
*[104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/) -[Solution](./Easy/104-maxDepth.js)
30+
*[107. Binary Tree Level Order Traversal II](https://leetcode.com/problems/binary-tree-level-order-traversal-ii/) -[Solution](./Easy/107-binaryTreeLevelTraversalII.js)
3031
*[110. Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/) -[Solution](./Easy/110-balancedBinaryTree.js)
3132
*[111. Minimum Depth of Binary Tree](https://leetcode.com/problems/minimum-depth-of-binary-tree/) -[Solution](./Easy/111-minimumDepthBinaryTree.js)
3233
*[112. Path Sum](https://leetcode.com/problems/path-sum/) -[Solution](./Easy/112-pathSum.js)
@@ -113,6 +114,7 @@
113114
*[94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) -[Solution](./Medium/94-binaryTreeInorder.js)
114115
*[96. Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/) -[Solution](./Medium/96-uniqueBinarySearchTrees.js)
115116
*[98. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) -[Solution](./Medium/98-validateBST.js)
117+
*[103. Binary Tree Zigzag Level Order Traversal](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/) -[Solution](./Medium/103-BSTZigzagLevelTraversal.js)
116118
*[108. Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/) -[Solution](./Medium/108-convertSortedArraytoBST.js)
117119
*[116. Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/) -[Solution](./Medium/116-PopulatingNextRightPointersinEachNode.js)
118120
*[121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) -[Solution](./Medium/121-bestTimeToBuySellStock.js)

0 commit comments

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