Skip to content

Commit 6a3b75c

Browse files
realDuYuanChaogithub-actions
realDuYuanChao
and
github-actions
authored
binary tree operation (examplehub#138)
* binary tree inorder traversal * binary tree operation * Formatted with Google Java Formatter Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
1 parent 5c64a8e commit 6a3b75c

8 files changed

Lines changed: 260 additions & 0 deletions

File tree

‎src/main/java/com/examplehub/leetcode/easy/BalancedBinaryTree.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package com.examplehub.leetcode.easy;
2+
3+
import com.examplehub.leetcode.TreeNode;
4+
5+
/** https://leetcode.com/problems/balanced-binary-tree/ */
6+
public class BalancedBinaryTree {
7+
public static boolean solution1(TreeNode root) {
8+
if (root == null) {
9+
return true;
10+
}
11+
return Math.abs(
12+
MaximumDepthOfBinaryTree.solution1(root.left)
13+
- MaximumDepthOfBinaryTree.solution1(root.right))
14+
<= 1
15+
&& solution1(root.left)
16+
&& solution1(root.right);
17+
}
18+
}

‎src/main/java/com/examplehub/leetcode/easy/BinaryTreeInorderTraversal.java‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.examplehub.leetcode.easy;
2+
3+
import com.examplehub.leetcode.TreeNode;
4+
import java.util.*;
5+
6+
public class BinaryTreeInorderTraversal {
7+
8+
public static void inOrder(TreeNode root, List<Integer> inOrderPath) {
9+
if (root != null) {
10+
inOrder(root.left, inOrderPath);
11+
inOrderPath.add(root.val);
12+
inOrder(root.right, inOrderPath);
13+
}
14+
}
15+
16+
public static List<Integer> solution1(TreeNode root) {
17+
List<Integer> inOrderPath = new ArrayList<>();
18+
inOrder(root, inOrderPath);
19+
return inOrderPath;
20+
}
21+
22+
public static List<Integer> solution2(TreeNode root) {
23+
List<Integer> inOrderPath = new ArrayList<>();
24+
Stack<TreeNode> stack = new Stack<>();
25+
TreeNode cur = root;
26+
while (cur != null || !stack.isEmpty()) {
27+
while (cur != null) {
28+
stack.push(cur);
29+
cur = cur.left;
30+
}
31+
cur = stack.pop();
32+
inOrderPath.add(cur.val);
33+
cur = cur.right;
34+
}
35+
return inOrderPath;
36+
}
37+
}

‎src/main/java/com/examplehub/leetcode/easy/MaximumDepthOfBinaryTree.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.examplehub.leetcode.easy;
2+
3+
import com.examplehub.leetcode.TreeNode;
4+
import java.util.LinkedList;
5+
import java.util.Queue;
6+
7+
public class MaximumDepthOfBinaryTree {
8+
public static int solution1(TreeNode root) {
9+
if (root == null) {
10+
return 0;
11+
}
12+
int leftHeight = solution1(root.left);
13+
int rightHeight = solution1(root.right);
14+
return Math.max(leftHeight, rightHeight) + 1;
15+
}
16+
17+
public static int solution2(TreeNode root) {
18+
if (root == null) {
19+
return 0;
20+
}
21+
Queue<TreeNode> queue = new LinkedList<>();
22+
queue.offer(root);
23+
int answer = 0;
24+
while (!queue.isEmpty()) {
25+
int size = queue.size();
26+
while (size > 0) {
27+
TreeNode node = queue.poll();
28+
assert node != null;
29+
if (node.left != null) {
30+
queue.offer(node.left);
31+
}
32+
if (node.right != null) {
33+
queue.offer(node.right);
34+
}
35+
size--;
36+
}
37+
answer++;
38+
}
39+
return answer;
40+
}
41+
}

‎src/main/java/com/examplehub/leetcode/easy/SymmetricTree.java‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.examplehub.leetcode.easy;
2+
3+
import com.examplehub.leetcode.TreeNode;
4+
import com.examplehub.strings.PalindromeString;
5+
import java.util.List;
6+
7+
/** https://leetcode.com/problems/symmetric-tree/ */
8+
public class SymmetricTree {
9+
public static boolean solution1(TreeNode root) {
10+
List<Integer> inOrderPath = BinaryTreeInorderTraversal.solution1(root);
11+
StringBuilder builder = new StringBuilder();
12+
for (Integer number : inOrderPath) {
13+
builder.append(number);
14+
}
15+
return PalindromeString.isPalindrome(builder.toString());
16+
}
17+
18+
public static boolean doSolution2(TreeNode left, TreeNode right) {
19+
if (left == null && right == null) {
20+
return true;
21+
}
22+
if (left == null || right == null) {
23+
return false;
24+
}
25+
if (left.val != right.val) {
26+
return false;
27+
}
28+
return doSolution2(left.left, right.right) && doSolution2(left.right, right.left);
29+
}
30+
31+
public static boolean solution2(TreeNode root) {
32+
if (root == null) {
33+
return true;
34+
}
35+
return doSolution2(root.left, root.right);
36+
}
37+
}

‎src/test/java/com/examplehub/leetcode/easy/BalancedBinaryTreeTest.java‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package com.examplehub.leetcode.easy;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import com.examplehub.leetcode.TreeNode;
6+
import com.examplehub.leetcode.utils.BinaryTreeUtils;
7+
import org.junit.jupiter.api.Test;
8+
9+
class BalancedBinaryTreeTest {
10+
@Test
11+
void testSolution1() {
12+
TreeNode root = BinaryTreeUtils.createTree(new int[] {3, 9, 20, -1, -1, 15, 7}, 0);
13+
assertTrue(BalancedBinaryTree.solution1(root));
14+
15+
root = BinaryTreeUtils.createTree(new int[] {1, 2, 2, 3, 3, -1, -1, 4, 4}, 0);
16+
assertFalse(BalancedBinaryTree.solution1(root));
17+
18+
root = BinaryTreeUtils.createTree(new int[] {}, 0);
19+
assertTrue(BalancedBinaryTree.solution1(root));
20+
}
21+
}

‎src/test/java/com/examplehub/leetcode/easy/BinaryTreeInorderTraversalTest.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.examplehub.leetcode.easy;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import com.examplehub.leetcode.TreeNode;
6+
import com.examplehub.leetcode.utils.BinaryTreeUtils;
7+
import org.junit.jupiter.api.Test;
8+
9+
class BinaryTreeInorderTraversalTest {
10+
@Test
11+
void testSolution1() {
12+
TreeNode root = BinaryTreeUtils.createTree(new int[] {1, -1, 2, -1, -1, 3}, 0);
13+
assertEquals("[1, 3, 2]", BinaryTreeInorderTraversal.solution1(root).toString());
14+
15+
root = BinaryTreeUtils.createTree(new int[] {}, 0);
16+
assertEquals("[]", BinaryTreeInorderTraversal.solution1(root).toString());
17+
18+
root = BinaryTreeUtils.createTree(new int[] {1}, 0);
19+
assertEquals("[1]", BinaryTreeInorderTraversal.solution1(root).toString());
20+
21+
root = BinaryTreeUtils.createTree(new int[] {1, 2}, 0);
22+
assertEquals("[2, 1]", BinaryTreeInorderTraversal.solution1(root).toString());
23+
24+
root = BinaryTreeUtils.createTree(new int[] {1, -1, 2}, 0);
25+
assertEquals("[1, 2]", BinaryTreeInorderTraversal.solution1(root).toString());
26+
}
27+
28+
@Test
29+
void testSolution2() {
30+
TreeNode root = BinaryTreeUtils.createTree(new int[] {1, -1, 2, -1, -1, 3}, 0);
31+
assertEquals("[1, 3, 2]", BinaryTreeInorderTraversal.solution2(root).toString());
32+
33+
root = BinaryTreeUtils.createTree(new int[] {}, 0);
34+
assertEquals("[]", BinaryTreeInorderTraversal.solution2(root).toString());
35+
36+
root = BinaryTreeUtils.createTree(new int[] {1}, 0);
37+
assertEquals("[1]", BinaryTreeInorderTraversal.solution2(root).toString());
38+
39+
root = BinaryTreeUtils.createTree(new int[] {1, 2}, 0);
40+
assertEquals("[2, 1]", BinaryTreeInorderTraversal.solution2(root).toString());
41+
42+
root = BinaryTreeUtils.createTree(new int[] {1, -1, 2}, 0);
43+
assertEquals("[1, 2]", BinaryTreeInorderTraversal.solution2(root).toString());
44+
}
45+
}

‎src/test/java/com/examplehub/leetcode/easy/MaximumDepthOfBinaryTreeTest.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package com.examplehub.leetcode.easy;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import com.examplehub.leetcode.TreeNode;
6+
import com.examplehub.leetcode.utils.BinaryTreeUtils;
7+
import org.junit.jupiter.api.Test;
8+
9+
class MaximumDepthOfBinaryTreeTest {
10+
@Test
11+
void testSolution1() {
12+
TreeNode root = BinaryTreeUtils.createTree(new int[] {3, 9, 20, -1, -1, 15, 7}, 0);
13+
assertEquals(3, MaximumDepthOfBinaryTree.solution1(root));
14+
15+
root = BinaryTreeUtils.createTree(new int[] {}, 0);
16+
assertEquals(0, MaximumDepthOfBinaryTree.solution1(root));
17+
18+
root = BinaryTreeUtils.createTree(new int[] {1, -1, 2}, 0);
19+
assertEquals(2, MaximumDepthOfBinaryTree.solution1(root));
20+
21+
root = BinaryTreeUtils.createTree(new int[] {0}, 0);
22+
assertEquals(1, MaximumDepthOfBinaryTree.solution1(root));
23+
}
24+
25+
@Test
26+
void testSolution2() {
27+
TreeNode root = BinaryTreeUtils.createTree(new int[] {3, 9, 20, -1, -1, 15, 7}, 0);
28+
assertEquals(3, MaximumDepthOfBinaryTree.solution2(root));
29+
30+
// root = BinaryTreeUtils.createTree(new int[]{}, 0);
31+
// assertEquals(0, MaximumDepthOfBinaryTree.solution2(root));
32+
//
33+
// root = BinaryTreeUtils.createTree(new int[]{1, -1, 2}, 0);
34+
// assertEquals(2, MaximumDepthOfBinaryTree.solution2(root));
35+
//
36+
// root = BinaryTreeUtils.createTree(new int[]{0}, 0);
37+
// assertEquals(1, MaximumDepthOfBinaryTree.solution2(root));
38+
}
39+
}

‎src/test/java/com/examplehub/leetcode/easy/SymmetricTreeTest.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package com.examplehub.leetcode.easy;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import com.examplehub.leetcode.TreeNode;
6+
import com.examplehub.leetcode.utils.BinaryTreeUtils;
7+
import org.junit.jupiter.api.Test;
8+
9+
class SymmetricTreeTest {
10+
11+
@Test
12+
void testSolution1() {
13+
TreeNode root = BinaryTreeUtils.createTree(new int[] {1, 2, 2, 3, 4, 4, 3}, 0);
14+
assertTrue(SymmetricTree.solution1(root));
15+
}
16+
17+
@Test
18+
void testSolution2() {
19+
TreeNode root = BinaryTreeUtils.createTree(new int[] {1, 2, 2, 3, 4, 4, 3}, 0);
20+
assertTrue(SymmetricTree.solution2(root));
21+
}
22+
}

0 commit comments

Comments
 (0)