[리트코드 94] Binary Tree Inorder Traversal

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번

트리순회 - 위키