[LeetCode] Binary Tree Inorder Traversal

문제 링크

Binary Tree Inorder Traversal - LeetCode

Can you solve this real interview question? Binary Tree Inorder Traversal - Given the root of a binary tree, return the inorder traversal of its nodes' values.   Example 1: Input: root = [1,null,2,3] Output: [1,3,2] Explanation: [https://assets.leetcode.com/uploads/2024/08/29/screenshot-2024-08-29-202743.png] Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [4,2,6,5,7,1,3,9,8] Explanation: [https://assets.leetcode.com/uploads/2024/08/29/tree_2.png] Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1]   Constraints: * The number of nodes in the tree is in the range [0, 100]. * -100 <= Node.val <= 100   Follow up: Recursive solution is trivial, could you do it iteratively?

https://leetcode.com/problems/binary-tree-inorder-traversal/

문제 요구 조건

• root라는 연결노드 배열을 매개변수로 받아요.

• 중위순회대로 숫자배열을 반환해야 돼요.

저의 문제풀이?

문제 풀이

최고의 성능을 낸 풀이방법

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let current = root;
    let stack = [];
    let ans = [];

    while(current || stack.length){
        while(current){
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        ans.push(current.val);
        current = current.right;
    }
    return ans;
};

사용된 변수 설명

• current
현재 방문 중인 노드를 가리키는 변수에요. 시작은 트리의 root 노드에요

• stack
아직 방문하지 않았지만, 나중에 다시 돌아와서 방문해야 될 부모 노드들을 임시로 저장하는 스택 자료구조에요.

• ans
중위 순회 결과를 저장하는 배열이에요.

1. 가장 왼쪽 노드까지 이동 및 스택에 노드 쌓기
• while(current) 루프는 현재 노드(current)가 null이 아닐 때까지 반복해요.
• 이 루프 안에서 current 노드를 스택에 푸시하고, current를 current.left 로 계속 업데이트 해요.
• 이 과정을 통해서 트리의 가장 왼쪽 끝 노드에 도달하게 되고, 그 경로에 있는 모든 부모 노드들이 스택에 차례대로 쌓이게 되죠.
• 이 단계가 끝나면 current는 null이 되고, 스택의 맨 위의 가장 왼쪽 노드가 위치하게 되요.

2. 노드 방문 및 오른쪽 자식으로 이동
• 바깥 쪽의 while(current || stack.length) 루프는 current가 null 이거나 스택에 노드가 남아있는 동안 계속 실행되어요
• 첫 번째 while가 끝나면, 스택에서 노드를 pop하여 current 에 할당 해요. 이 노드가 바로 트리의 가장 왼쪽 노드인 거죠.
• ans.push(current.val) 코드를 통해 이 노드의 값을 결과 배열에 추가해요.
• 그리고 current = current.right 코드를 통해 current 를 오른쪽 자식 노드로 업데이트해요. 이제 다음 순회는 오른쪽 자식 노드부터 시작하는 거죠.
• 만약 오른쪽 자식 노드가 있다면, 바깥 while 루프의 다음 반복에서 다시 첫 번째 while 루프로 진입해서 그 노드의 가장 왼쪽 자식까지 탐색을 해요.
• 만약 오른쪽 자식 노드가 없다면, current는 null이 되고, 스택에서 다음 노드를 팝하여 방문하게 되어요.