[LeetCode/Easy] 94. Binary Tree Inorder Traversal

1. Input

1) TreeNode root

 

2. Output

1) root를 중위순회한 결과를 담은 리스트를 반환

 

3. Constraint

1) root의 노드의 개수는 [0, 100]

2) -100 <= Node.val <= 100

 

4. Example

Input: root = [1,null,2,3] -> Output: [1,3,2]

 

5. Code

1) 첫 코드(2023/05/09)

/**
 * 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> inorder = new ArrayList<>();
        if(root!=null){
            if(root.left!=null)
                inorder.addAll(inorderTraversal(root.left));
            inorder.add(root.val);
            if(root.right!=null)
                inorder.addAll(inorderTraversal(root.right));

        }
        return inorder;
    }
}

2) 스택을 이용한 다른 사람의 코드(2023/05/09)

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();

    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;

    while(cur!=null || !stack.empty()){
        while(cur!=null){
            stack.add(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
    }

    return list;
}