Add binary tree code

jbee37142 · jbee37142 · commit d98f33f52fd1 · 2017-05-31T20:15:27.000+09:00
diff --git a/src/test/java/datastructure/binaryTree/BinaryTree.java b/src/test/java/datastructure/binaryTree/BinaryTree.java
@@ -0,0 +1,149 @@
+package datastructure.binaryTree;
+
+import org.junit.Test;
+
+import static org.hamcrest.CoreMatchers.is;
+import static org.junit.Assert.assertThat;
+
+public class BinaryTree {
+
+    @Test
+    public void test() {
+        Node node1 = new Node();
+        Node node2 = new Node();
+        Node node3 = new Node();
+        Node node4 = new Node();
+        node1.data = 1;
+        node2.data = 2;
+        node3.data = 3;
+        node4.data = 4;
+        node1.left = node2;
+        node1.right = node3;
+        node2.left = node4;
+
+        assertThat(getMax(node1), is(4));
+    }
+
+
+    /*
+        TASK
+        바이너리 트리에서 최대값을 구한다.
+     */
+
+    public int getMax(Node root) {
+        int result = Integer.MAX_VALUE;
+        if (root == null) {
+            return result;
+        }
+        return getMaxRec(root, result);
+    }
+
+    public int getMaxRec(Node head, int result) {
+        if (head == null) {
+            return result;
+        }
+        if (head.data > result) {
+            result = head.data;
+        }
+        result = getMaxRec(head.left, result);
+        result = getMaxRec(head.right, result);
+        return result;
+    }
+
+
+    /*
+        TASK
+        주어진 바이너리 트리가 균형 잡힌 트리인지 판별한다.
+     */
+
+    public boolean isBalanced(Node root) {
+        return getNodeHeight(root) != -1;
+    }
+
+    private int getNodeHeight(Node node) {
+        if (node == null) {
+            return 0;
+        }
+        int leftHeight = getNodeHeight(node.left);
+        if (leftHeight == -1) {
+            return -1;
+        }
+
+        int rightHeight = getNodeHeight(node.right);
+        if (rightHeight == -1) {
+            return -1;
+        }
+
+        if (Math.abs(rightHeight - leftHeight) > 1) {
+            return -1;
+        }
+
+        return Math.max(leftHeight, rightHeight) + 1;
+    }
+
+
+    /*
+        TASK
+        오름차순으로 정렬된 배열을 Binary Search Tree로 변환한다.
+        트리의 높이를 최소화 하면서 (즉 complete binary tree로) 변환한다.
+     */
+
+    public Node buildBST(int[] arr) {
+        return buildBSTRec(arr, 0, arr.length - 1);
+    }
+
+    private Node buildBSTRec(int[] arr, int start, int end) {
+        if (start > end) {
+            return null;
+        }
+        int middle = start + (end - start)/2;
+        Node leftNode = buildBSTRec(arr, start, middle - 1);
+        Node rightNode = buildBSTRec(arr, middle + 1, end);
+
+        return new Node(arr[middle], leftNode, rightNode);
+    }
+
+
+    /*
+        TASK
+        주어진 트리가 BST인지 확인한다.
+        Hint: 범위 탐색
+     */
+
+    public boolean isBST(Node root) {
+        return isBSTRec(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
+    }
+
+    private boolean isBSTRec(Node node, int min, int max) {
+        if (node == null) {
+            return true;
+        }
+
+        if (node.data <= min || node.data > max) {
+            return false;
+        }
+
+        boolean isBSTOfLeft = isBSTRec(node.left, min, node.data);
+        boolean isBSTOfRight = isBSTRec(node.right, node.data, max);
+
+        return isBSTOfLeft && isBSTOfRight;
+    }
+
+
+    public class Node {
+        int data;
+        Node left;
+        Node right;
+
+        public Node() {}
+        public Node(int data) {
+            this.data = data;
+        }
+
+        public Node(int data, Node left, Node right) {
+            this.data = data;
+            this.left = left;
+            this.right = right;
+        }
+    }
+}
