[LeetCode/94/Java]Binary Tree Inorder Traversal

[LeetCode/94/Java]Binary Tree Inorder Traversal

풀이

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {

    	List<Integer> result = new LinkedList<Integer>();
    	inorderTraversal(root, result);
		return result;
    }
    
    public List<Integer> inorderTraversal(TreeNode root, List<Integer> list) {
    	
    	if(root == null) return list;
    	
    	list = inorderTraversal(root.left, list);
    	list.add(root.val);
    	list = inorderTraversal(root.right, list);
    	
    	return list;
    }
}

후기

중위순회 처리 알고리즘 문제입니다.

왼쪽의 마지막 노드까지 재귀호출을 하고 루트로 돌아온다음에 오른쪽 노드도 왼쪽부터 차례대로 탐색해 나갑니다.

 

time complexity O(N)
space complexity O(N)