개발하는 두더지

[리트코드 94] Binary Tree Inorder Traversal 본문

알고리즘

[리트코드 94] Binary Tree Inorder Traversal

덜지 2018. 9. 15. 00:58

import java.util.*;

/**
* 이진트리
* input 1 null 2 3
* output 1 3 2
* inorder      left self right
* preorder     self left right
* postorder    left right self
*/
public class Test {

List<Integer> ret;

public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode t1 = new TreeNode(2);
TreeNode t2 = new TreeNode(3);
root.right = t1;
t1.left = t2;

Test test = new Test();
for(Integer i : test.inorderTraversal(root)) {
System.out.print(i + " ");
}

System.out.println();

for(Integer i : test.preorderTraversal(root)) {
System.out.print(i + " ");
}

System.out.println();

for(Integer i : test.postorderTraversal(root)) {
System.out.print(i + " ");
}
}

public List<Integer> inorderTraversal(TreeNode root) {
ret = new ArrayList<Integer>();
inorderTraverse(root);
return ret;
}

public List<Integer> preorderTraversal(TreeNode root) {
ret = new ArrayList<Integer>();
preorderTraverse(root);
return ret;
}

public List<Integer> postorderTraversal(TreeNode root) {
ret = new ArrayList<Integer>();
postorderTraverse(root);
return ret;
}

private void preorderTraverse(TreeNode self) {
if(self == null) return;
ret.add(self.val);
preorderTraverse(self.left);
preorderTraverse(self.right);
}

private void inorderTraverse(TreeNode self) {
if(self == null) return;
inorderTraverse(self.left);
ret.add(self.val);
inorderTraverse(self.right);
}

private void postorderTraverse(TreeNode self) {
if(self == null) return;
postorderTraverse(self.left);
postorderTraverse(self.right);
ret.add(self.val);
}
}

class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int i) { val = i; }
}


문제는 아래와 같이 주어집니다.


Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?


[결과]

1 3 2

1 2 3

3 2 1


[필요 개념]

1. 트리순회

inorder  중위순회는 왼쪽노드 -> 자신 -> 오른쪽 노드

preorder 전위순회는 자신 -> 왼쪽노드 -> 오른쪽 노드

postorder 후위순회는 왼쪽노드 -> 오른쪽노드 -> 자신


2. 재귀호출



면접코딩

리트코드 94번

트리순회 - 위키


Comments