이번에 풀어본 leetcode는 invert tree이다. 항상 기본기가 중요하므로, tree를 구현하는 것 부터 시작을 한다. 이렇게 하면 시간이 오래 걸리지만, 그만큼 tree에 대한 이해도가 깊어지게 되므로 결코 시간 낭비가 아니게 된다. 따라서 앞으로 tree 관련한 leetcode 문제를 풀 때, 나는 매번 tree를 새롭게 구현하고 나서 풀어갈 생각이다.
package Trees;
public class MyBinaryTree {
public static final String IN_ORDER_TRAVERSE = "inorder";
public static final String PRE_ORDER_TRAVERSE = "preorder";
public static final String POST_ORDER_TRAVERSE = "postorder";
private TreeNode root;
private int nodeCounter = 0;
private class TreeNode {
private int data;
private TreeNode leftChild;
private TreeNode rightChild;
public TreeNode(int data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
public TreeNode getLeftNode() {
return leftChild;
}
public void setLeftNode(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightNode() {
return rightChild;
}
public void setRightNode(TreeNode rightChild) {
this.rightChild = rightChild;
}
public int getData() {
return data;
}
}
public boolean search(int data) {
TreeNode currentNode = root;
while (currentNode != null) {
if (currentNode.getData() == data) {
return true;
} else if (currentNode.getData() > data) {
currentNode = currentNode.getLeftNode();
} else {
currentNode = currentNode.getRightNode();
}
}
return false;
}
public boolean addData(int data) {
TreeNode newNode = new TreeNode(data);
if (search(data)) {
return false;
}
if (root == null) {
root = newNode;
nodeCounter++;
return true;
}
TreeNode currentNode = root;
TreeNode parentNode;
while (true) {
parentNode = currentNode;
if (data < currentNode.getData()) {
currentNode = currentNode.getLeftNode();
if (currentNode == null) {
parentNode.setLeftNode(newNode);
nodeCounter++;
return true;
}
} else if (data > currentNode.getData()) {
currentNode = currentNode.getRightNode();
if (currentNode == null) {
parentNode.setRightNode(newNode);
nodeCounter++;
return true;
}
}
}
}
public TreeNode invertTree(TreeNode node) {
if (node == null) {
return null;
}
// 왼쪽과 오른쪽 자식 노드를 바꾼다.
TreeNode temp = node.leftChild;
node.leftChild = node.rightChild;
node.rightChild = temp;
// 왼쪽과 오른쪽 서브트리도 뒤집는다.
invertTree(node.leftChild);
invertTree(node.rightChild);
return node;
}
public void invertAndPrintTree() {
System.out.println("Before inverted Tree: ");
printNode(IN_ORDER_TRAVERSE);
root = invertTree(root);
System.out.println("Inverted Tree: ");
printNode(IN_ORDER_TRAVERSE);
System.out.println();
}
// A
// B C
//
// in-order: follow the order from left to right, B A C
// pre-order: read root first and follow the order from left to right: A B C
// post-order: read root last and follow the order from left to right: B C A
private void inOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.getLeftNode());
System.out.printf("%d ", node.getData());
inOrderTraversal(node.getRightNode());
}
private void preOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
System.out.printf("%d ", node.getData());
preOrderTraversal(node.getLeftNode());
preOrderTraversal(node.getRightNode());
}
private void postOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
postOrderTraversal(node.getLeftNode());
postOrderTraversal(node.getRightNode());
System.out.printf("%d ", node.getData());
}
public int getNodeCounter() {
return nodeCounter;
}
public void printNode(String mode) {
switch (mode) {
case PRE_ORDER_TRAVERSE:
preOrderTraversal(root);
System.out.println("\n" + getNodeCounter());
break;
case POST_ORDER_TRAVERSE:
postOrderTraversal(root);
System.out.println("\n" + getNodeCounter());
break;
case IN_ORDER_TRAVERSE:
default:
inOrderTraversal(root);
System.out.println("\n" + getNodeCounter());
break;
}
}
public static void main(String[] args) {
MyBinaryTree myBT = new MyBinaryTree();
int[] data = { 25, 15, 10, 4, 12, 22, 18, 24, 31, 35, 44, 70, 66, 90 };
for (int value : data) {
myBT.addData(value);
}
System.out.println(IN_ORDER_TRAVERSE);
myBT.printNode(IN_ORDER_TRAVERSE);
System.out.println();
System.out.println(PRE_ORDER_TRAVERSE);
myBT.printNode(PRE_ORDER_TRAVERSE);
System.out.println();
System.out.println(POST_ORDER_TRAVERSE);
myBT.printNode(POST_ORDER_TRAVERSE);
System.out.println();
myBT.invertAndPrintTree();
}
}
MyBinaryTree의 구조는 다소 복잡해 보이나, 해부를 해보면 그리 복잡하지 않다. 아래의 hierarchy를 참고하면 되겠다.
- MyBinaryTree class
- Members
- IN_ORDER_TRAVERSE
- PRE_ORDER_TRAVERSE
- POST_ORDER_TRAVERSE
- root
- nodeCounter
- Class
- TreeNode
- Members
- data
- leftChild
- rightChild
- Methods
- Constructor
- getLeftNode
- setLeftNode
- getRightNode
- setRightNode
- getData
- Members
- TreeNode
- Methods
- search
- addData
- inOrderTraversal
- postOrderTraversal
- preOrderTraversal
- printNode
- invertTree
- invertAndPrintTree
- main
- Members
invertTree 메서드는 트리를 뒤집는 작업을 하는데, 이건 주어진 노드와 그 하위 노드들을 재귀적으로 뒤집는 과정을 포함한다. 자세한 동작 순서와 예시를 아래에 설명하겠다.
예를 들어, 이렇게 생긴 이진 트리가 있다고 하자.
4
/ \
2 7
/ \ / \
1 3 6 9
-
루트 노드(4)에서 시작한다. 루트 노드의 왼쪽 자식과 오른쪽 자식을 서로 바꾼다.
- 왼쪽 자식: 2 → 7
- 오른쪽 자식: 7 → 2
-
루트 노드의 왼쪽 자식 노드(이제는 7)로 넘어간다.
- 7의 왼쪽 자식: 6 → 9
- 7의 오른쪽 자식: 9 → 6
-
7의 왼쪽과 오른쪽 자식 노드는 더 이상 자식이 없으므로 더 이상 뒤집지 않는다.
-
루트 노드의 오른쪽 자식 노드(이제는 2)로 넘어간다.
- 2의 왼쪽 자식: 1 → 3
- 2의 오른쪽 자식: 3 → 1
-
2의 왼쪽과 오른쪽 자식 노드도 더 이상 자식이 없으므로 더 이상 뒤집지 않는다.
작업이 끝나면, 트리는 이렇게 뒤집힌다.
4
/ \
7 2
/ \ / \
9 6 3 1
이렇게 재귀적으로 각 노드를 방문하면서 왼쪽과 오른쪽 자식을 바꾸는 과정을 거치면, 트리는 완전히 뒤집힌다. 이게 invertTree 메서드의 동작 방식이다.
댓글 없음:
댓글 쓰기