Skip to content

Commit bbfe9cb

Browse files
kanahaiyakanahaiya
committed
Added more trees problem solutions inside medium level category
1 parent 02879f5 commit bbfe9cb

File tree

4 files changed

+181
-43
lines changed

4 files changed

+181
-43
lines changed

‎LeetCodeSolutions/MediumLevelSolutions/.settings/org.eclipse.jdt.core.prefs

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
11
eclipse.preferences.version=1
22
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
3-
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.5
4-
org.eclipse.jdt.core.compiler.compliance=1.5
3+
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.8
4+
org.eclipse.jdt.core.compiler.compliance=1.8
55
org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
66
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
77
org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
8-
org.eclipse.jdt.core.compiler.source=1.5
8+
org.eclipse.jdt.core.compiler.source=1.8

‎LeetCodeSolutions/MediumLevelSolutions/src/main/java/com/javaaid/solutions/medium/trees/ConstructBinaryTreeFromInorderAndPostorderTraversal.java

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
/**
2+
*
3+
*/
4+
package com.javaaid.solutions.medium.trees;
5+
6+
/**
7+
* @author Kanahaiya Gupta
8+
*
9+
*/
10+
public class ConstructBinaryTreeFromInorderAndPostorderTraversal {
11+
12+
static class TreeNode {
13+
int val;
14+
TreeNode left;
15+
TreeNode right;
16+
17+
TreeNode(int x) {
18+
val = x;
19+
}
20+
}
21+
class Level{
22+
int index=0;
23+
}
24+
25+
public TreeNode buildTree(int[] inorder, int[] postorder) {
26+
Level lvl=new Level();
27+
lvl.index=postorder.length-1;
28+
TreeNode root=buildTreeUtil(inorder,postorder,0,postorder.length-1,lvl);
29+
return root;
30+
}
31+
32+
/**
33+
*
34+
* @param inorder
35+
* @param postorder
36+
* @param start
37+
* @param end
38+
* @param lvl
39+
* @return
40+
*/
41+
private TreeNode buildTreeUtil(int[] inorder, int[] postorder, int start, int end, Level lvl) {
42+
if(start<=end) {
43+
TreeNode midNode=new TreeNode(postorder[lvl.index--]);
44+
if(start==end)return midNode;
45+
int inIndex=searchKey(inorder, start, end, midNode.val);
46+
midNode.right=buildTreeUtil(inorder,postorder,inIndex+1,end,lvl);
47+
midNode.left=buildTreeUtil(inorder,postorder,start,inIndex-1,lvl);
48+
return midNode;
49+
}
50+
return null;
51+
}
52+
53+
/**
54+
*
55+
* @param inorder
56+
* @param start
57+
* @param end
58+
* @param val
59+
* @return
60+
*/
61+
private int searchKey(int[] inorder, int start, int end, int val) {
62+
for (int i = start; i <= end; i++) {
63+
if (inorder[i] == val)
64+
return i;
65+
}
66+
return -1;
67+
}
68+
}

‎LeetCodeSolutions/MediumLevelSolutions/src/main/java/com/javaaid/solutions/medium/trees/ConstructBinaryTreeFromPreorderAndInorderTraversal.java

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
/**
2+
*
3+
*/
4+
package com.javaaid.solutions.medium.trees;
5+
6+
/**
7+
* @author Kanahaiya Gupta
8+
*
9+
*/
10+
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
11+
static class TreeNode {
12+
int val;
13+
TreeNode left;
14+
TreeNode right;
15+
16+
TreeNode(int x) {
17+
val = x;
18+
}
19+
}
20+
21+
class Level {
22+
int index = 0;
23+
}
24+
25+
public TreeNode buildTree(int[] preorder, int[] inorder) {
26+
Level lvl = new Level();
27+
TreeNode root = buildTreeUtil(preorder, inorder, 0, preorder.length - 1, lvl);
28+
return root;
29+
}
30+
31+
/**
32+
*
33+
* @param preorder
34+
* @param inorder
35+
* @param start
36+
* @param end
37+
* @param lvl
38+
* @return
39+
*/
40+
private TreeNode buildTreeUtil(int[] preorder, int[] inorder, int start, int end, Level lvl) {
41+
if (start <= end) {
42+
TreeNode midNode = new TreeNode(preorder[lvl.index++]);
43+
if (start == end)
44+
return midNode;
45+
int inIndex = searchKey(inorder, start, end, midNode.val);
46+
midNode.left = buildTreeUtil(preorder, inorder, start, inIndex - 1, lvl);
47+
midNode.right = buildTreeUtil(preorder, inorder, inIndex + 1, end, lvl);
48+
return midNode;
49+
}
50+
return null;
51+
}
52+
53+
/**
54+
*
55+
* @param inorder
56+
* @param start
57+
* @param end
58+
* @param val
59+
* @return
60+
*/
61+
private int searchKey(int[] inorder, int start, int end, int val) {
62+
for (int i = start; i <= end; i++) {
63+
if (inorder[i] == val)
64+
return i;
65+
}
66+
return -1;
67+
}
68+
}

0 commit comments

Comments
 (0)