8000 [LEET-513] add 513 · aduispace/Leetcode-1@4b081cd · GitHub
[go: up one dir, main page]
Skip to content

Commit 4b081cd

Browse files
fishercoder1534fishercoder1534
committed
[LEET-513] add 513
1 parent 525cbb5 commit 4b081cd

File tree

3 files changed

+112
-0
lines changed

3 files changed

+112
-0
lines changed

‎leetcode-algorithms/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
## Algorithms
44
| # | Title | Solutions | Time | Space | Difficulty | Tag | Notes
55
|-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
6+
|513|[Find Left Most Element](https://leetcode.com/problems/find-left-most-element/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/FindLeftMostElement.java) | O(n) |O(k) | Medium| BFS
67
|504|[Base 7](https://leetcode.com/problems/base-7/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/Base7.java) | O(1) |O(1) | Easy|
78
|501|[Find Mode in Binary Tree](https://leetcode.com/problems/find-mode-in-binary-tree/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/FindModeinBinaryTree.java) | O(n) |O(k) | Easy| Binary Tree
89
|492|[Construct the Rectangle](https://leetcode.com/problems/construct-the-rectangle/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ConstructTheRectangle.java) | O(n) |O(1) | Easy| Array

‎leetcode-algorithms/src/main/java/com/stevesun/solutions/FindLeftMostElement.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package com.stevesun.solutions;
2+
3+
import com.stevesun.common.classes.TreeNode;
4+
5+
import java.util.LinkedList;
6+
import java.util.Queue;
7+
8+
/**
9+
* Given a binary tree, find the leftmost value in the last row of the tree.
10+
11+
Example 1:
12+
Input:
13+
14+
2
15+
/ \
16+
1 3
17+
18+
Output:
19+
1
20+
Example 2:
21+
Input:
22+
23+
24+
1
25+
/ \
26+
2 3
27+
/ / \
28+
4 5 6
29+
/
30+
7
31+
32+
Output:
33+
7
34+
Note: You may assume the tree (i.e., the given root node) is not NULL.
35+
*/
36+
public class FindLeftMostElement {
37+
38+
public int findLeftMostNode(TreeNode root) {
39+
Queue<TreeNode> queue = new LinkedList<>();
40+
queue.offer(root);
41+
TreeNode leftMost = root;
42+
while (!queue.isEmpty()){
43+
int size = queue.size();
44+
for (int i = 0; i < size; i++){
45+
TreeNode curr = queue.poll();
46+
if (i == 0){
47+
leftMost = curr;
48+
}
49+
if (curr.left != null) queue.offer(curr.left);
50+
if (curr.right != null) queue.offer(curr.right);
51+
}
52+
}
53+
return leftMost.val;
54+
}
55+
}

‎leetcode-algorithms/src/test/java/com/stevesun/FindLeftMostElementTest.java

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.common.classes.TreeNode;
4+
import com.stevesun.solutions.FindLeftMostElement;
5+
import org.junit.Before;
6+
import org.junit.BeforeClass;
7+
import org.junit.Test;
8+
9+
import static junit.framework.Assert.assertEquals;
10+
11+
/**
12+
* Created by stevesun on 1/15/17.
13+
*/
14+
public class FindLeftMostElementTest {
15+
private static FindLeftMostElement test;
16+
private static int expected;
17+
private static int actual;
18+
private static TreeNode root;
19+
20+
@BeforeClass
21+
public static void setup(){
22+
test = new FindLeftMostElement();
23+
}
24+
25+
@Before
26+
public void setupForEachTest(){
27+
expected = 0;
28+
actual = 0;
29+
root = new TreeNode(0);
30+
}
31+
32+
@Test
33+
public void test1(){
34+
TreeNode root = new TreeNode(2);
35+
root.left = new TreeNode(1);
36+
root.right= new TreeNode(3);
37+
expected = 1;
38+
actual = test.findLeftMostNode(root);
39+
assertEquals(expected, actual);
40+
41+
}
42+
43+
@Test
44+
public void test2(){
45+
TreeNode root = new TreeNode(1);
46+
root.left = new TreeNode(2);
47+
root.right= new TreeNode(3);
48+
root.left.left= new TreeNode(4);
49+
root.right.left= new TreeNode(5);
50+
root.right.right= new TreeNode(6);
51+
root.right.left.left= new TreeNode(7);
52+
expected = 7;
53+
actual = test.findLeftMostNode(root);
54+
assertEquals(expected, actual);
55+
}
56+
}

0 commit comments

Comments
 (0)
0