Binary Tree Inorder Traversal

from __future__ import annotations
from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(
        self,
        val: int = 0,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """
    LeetCode 94 - Binary Tree Inorder Traversal
    中順走査（左→根→右）を明示スタックによる反復で実装。

    Time:  O(N) - 全ノードを一度だけ訪問
    Space: O(N) - 明示スタックの最大深さ（最悪: 左偏木で N）
    """

    def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        # ── ガード: 空木は即座に空リストを返す
        if root is None:
            return []

        result: list[int] = []          # 中順走査の結果
        stack: list[TreeNode] = []      # 明示スタック（非 None のみ格納）
        cur: Optional[TreeNode] = root  # 現在注目しているノード

        while cur is not None or stack:

            # Ph1: 左端まで潜りながらスタックに積む
            while cur is not None:
                stack.append(cur)   # 右・自身は後回し
                cur = cur.left      # 左へ進む

            # Ph2: スタック top を取り出して訪問
            node: TreeNode = stack.pop()
            result.append(node.val)  # ← 中順で値を記録

            # Ph3: 右部分木へカーソルを移す
            cur = node.right  # None なら次ループで即 Ph2 へ

        return result

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/**
 * Binary Tree Inorder Traversal（反復・明示スタック実装）
 * @complexity Time: O(N), Space: O(N)
 */
function inorderTraversal(root: TreeNode | null): number[] {
    if (root === null) return [];

    const result: number[]   = [];
    const stack: TreeNode[]  = [];
    let current: TreeNode | null = root;

    while (current !== null || stack.length > 0) {

        // Ph1: 左端まで潜る
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }

        // Ph2: 訪問
        const node = stack.pop()!;   // stack.length > 0 保証済み
        result.push(node.val);

        // Ph3: 右へ移動
        current = node.right;
    }

    return result;
}

// use std::rc::Rc; use std::cell::RefCell; // LeetCode 環境で提供済み

/// Binary Tree Inorder Traversal（反復・明示スタック実装）
///
/// # Complexity
/// - Time:  O(N)
/// - Space: O(N)
pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    if root.is_none() { return vec![]; }

    let mut result: Vec<i32>                    = Vec::new();
    let mut stack:  Vec<Rc<RefCell<TreeNode>>>  = Vec::new();
    let mut current = root;

    while current.is_some() || !stack.is_empty() {

        // Ph1: 左端まで潜りながらスタックに積む
        while let Some(node_rc) = current {
            stack.push(Rc::clone(&node_rc));
            let left = node_rc.borrow().left.clone();
            current = left;
        }

        // Ph2: スタック top を取り出して訪問
        if let Some(node_rc) = stack.pop() {
            let (val, right) = {
                let node = node_rc.borrow();
                (node.val, node.right.clone())
            }; // Ref が drop され借用解放

            result.push(val);

            // Ph3: 右部分木へカーソルを移す
            current = right;
        }
    }

    result
}