最下段の左端ノード値の取得

指定された二叉樹に対して、最下層に位置する左端のノードが保持する数値を特定します。幅優先探索（BFS）を用いて木を階層ごとに処理し、各レベルの走査開始時に最初に訪問するノードを記録します。探索が完全に終了した時点で最後に記録された値が、要件を満たす最下段左端ノードの値となります。このアプローチにより、キューの順序を意図的に逆転させる必要がなくなり、視認性と拡張性が向上します。

class Solution {
public:
    int findBottomLeftValue(TreeNode* rootNode) {
        std::queue<TreeNode*> explorationQueue;
        explorationQueue.push(rootNode);
        TreeNode* leftmostNode = rootNode;

        while (!explorationQueue.empty()) {
            int levelSize = explorationQueue.size();
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* current = explorationQueue.front();
                explorationQueue.pop();
                
                if (i == 0) {
                    leftmostNode = current;
                }
                if (current->left) explorationQueue.push(current->left);
                if (current->right) explorationQueue.push(current->right);
            }
        }
        return leftmostNode->val;
    }
};

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        bfs_queue = deque([root])
        leftmost_val = root.val
        while bfs_queue:
            level_count = len(bfs_queue)
            for i in range(level_count):
                current_node = bfs_queue.popleft()
                if i == 0:
                    leftmost_val = current_node.val
                if current_node.left:
                    bfs_queue.append(current_node.left)
                if current_node.right:
                    bfs_queue.append(current_node.right)
        return leftmost_val

ルートから葉へのパス和の検証

二叉樹の根ノードから葉ノードに至る経路上の値の合計が、指定された目標値と一致するかを判定します。再帰呼び出しによるコールスタックの消費を抑えるため、明示的なスタック構造を用いた反復的な深さ優先探索（DFS）を実装します。各ノードへの移動時に累計値を更新し、子ノードを持たない葉ノードに到達した時点で目標値との一致を検証します。探索中に条件を満たす経路が発見されれば即時に成功判定を返却します。

class Solution {
public:
    bool hasPathSum(TreeNode* rootNode, int targetValue) {
        if (!rootNode) return false;
        std::stack<std::pair<TreeNode*, int>> traversalStack;
        traversalStack.push({rootNode, rootNode->val});

        while (!traversalStack.empty()) {
            auto [currentNode, currentSum] = traversalStack.top();
            traversalStack.pop();

            bool isLeaf = !currentNode->left && !currentNode->right;
            if (isLeaf && currentSum == targetValue) return true;

            if (currentNode->right) {
                traversalStack.push({currentNode->right, currentSum + currentNode->right->val});
            }
            if (currentNode->left) {
                traversalStack.push({currentNode->left, currentSum + currentNode->left->val});
            }
        }
        return false;
    }
};

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        stack = [(root, root.val)]
        while stack:
            node, current_sum = stack.pop()
            if not node.left and not node.right:
                if current_sum == targetSum:
                    return True
            if node.right:
                stack.append((node.right, current_sum + node.right.val))
            if node.left:
                stack.append((node.left, current_sum + node.left.val))
        return False

中序・後序配列からの二叉树再構成

与えられた中序（inorder）および後序（postorder）の整数配列をもとに、元の二叉樹を再構築します。配列の分割処理に伴うメモリコピーコストを排除するため、インデックス範囲を引数として受け取る再帰関数を設計します。中序配列における値とインデックスの対応関係をハッシュマップで事前に変換しておくことで、ルートノードの位置特定を定数時間で行えるように最適化します。後序配列の末尾要素が常に現在の部分木におけるルートになる性質を活用し、右部分木から順に再帰的に構築を進めます。

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        value_to_index = {val: idx for idx, val in enumerate(inorder)}
        post_idx = len(postorder) - 1

        def construct_subtree(in_start: int, in_end: int) -> Optional[TreeNode]:
            nonlocal post_idx
            if in_start > in_end:
                return None

            root_val = postorder[post_idx]
            post_idx -= 1
            root_node = TreeNode(root_val)

            root_idx = value_to_index[root_val]
            # 後序配列の特性上、右部分木を先に再帰的に構築する
            root_node.right = construct_subtree(root_idx + 1, in_end)
            root_node.left = construct_subtree(in_start, root_idx - 1)
            return root_node

        return construct_subtree(0, len(inorder) - 1)

class Solution {
private:
    std::unordered_map<int, int> value_map;
    int post_idx;
    
    TreeNode* buildHelper(const std::vector<int>& in_seq, const std::vector<int>& post_seq, int in_left, int in_right) {
        if (in_left > in_right) return nullptr;

        int root_val = post_seq[post_idx];
        TreeNode* node = new TreeNode(root_val);
        post_idx--;
        int mid = value_map[root_val];

        node->right = buildHelper(in_seq, post_seq, mid + 1, in_right);
        node->left = buildHelper(in_seq, post_seq, in_left, mid - 1);
        return node;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        post_idx = postorder.size() - 1;
        for (int i = 0; i < inorder.size(); ++i) {
            value_map[inorder[i]] = i;
        }
        return buildHelper(inorder, postorder, 0, inorder.size() - 1);
    }
};