From 0b70c909e6a8360a376da50e9a9862f12e168384 Mon Sep 17 00:00:00 2001
From: Michael Hunteman <michael@huntm.net>
Date: Tue, 18 Oct 2022 22:54:10 -0500
Subject: Add Build Tree

---
 BuildTree.java | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)
 create mode 100644 BuildTree.java

diff --git a/BuildTree.java b/BuildTree.java
new file mode 100644
index 0000000..524a7a1
--- /dev/null
+++ b/BuildTree.java
@@ -0,0 +1,77 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class BuildTree {
+	// My old solution
+	/*
+	public static TreeNode buildTree(int[] preorder, int[] inorder) {
+		TreeNode root = new TreeNode(preorder[0]);
+		Stack<TreeNode> stack = new Stack<TreeNode>();
+		stack.push(root);
+		int parentIndex = 1;
+		boolean left = true;
+		for (int i = 1; i < preorder.length; i++) {
+			TreeNode node = new TreeNode(preorder[i]);
+			for (int j = 0; j < inorder.length; j++) {
+				if (node.val == inorder[j]) {
+					if (j < parentIndex) {
+						left = true;
+						stack.peek().left = node;
+						System.out.println("Left: " + node.val);
+					} else if (left) {
+						left = false;
+						stack.pop();
+						stack.peek().right = node;
+						System.out.println("Right: " + node.val);
+					} else {
+						stack.peek().right = node;
+						System.out.println(stack.peek().val);
+						System.out.println("Right: " + node.val);
+					}
+					parentIndex = j;
+					break;
+				}
+			}
+			stack.push(node);
+		}
+		return root;
+	}
+	*/
+
+	private static int preIndex = 0;
+
+	public static int findInorder(int value, int[] inorder) {
+		for (int i = 0; i < inorder.length; i++) {
+			if (inorder[i] == value)
+				return i;
+		}
+		return -1;
+	}
+
+	public static TreeNode
+	buildTree(int[] preorder, int[] inorder, int start, int end) {
+		if (start > end)
+			return null;
+		int value = preorder[preIndex++];
+		TreeNode node = new TreeNode(value);
+		if (start == end)
+			return node;
+		int mid = findInorder(value, inorder);
+		node.left = buildTree(preorder, inorder, start, mid - 1);
+		node.right = buildTree(preorder, inorder, mid + 1, end);
+		return node;
+	}
+
+	public static void main(String[] args) {
+		TreeNode leftLeaf = new TreeNode(9);
+		TreeNode middleLeaf = new TreeNode(15);
+		TreeNode rightLeaf = new TreeNode(7);
+		TreeNode rightParent = new TreeNode(20, middleLeaf, rightLeaf);
+		TreeNode root = new TreeNode(3, leftLeaf, rightParent);
+		int[] preorder = {3, 9, 20, 15, 7};
+		int[] inorder = {9, 3, 15, 20, 7};
+		int n = preorder.length - 1;
+		System.out.println(buildTree(preorder, inorder, 0, n).right.right.val);
+	}
+}
-- 
cgit v1.2.3