# LeetCode Medium 94. Binary Tree Inorder Traversal

tags: leetcode

問題

• Explore
• Problems

二分木を与えられた時, そのノードの値のinorder traversalを返せ

追加:

再帰的な解法はありきたりである. 反復的に解くことはできるか?

解法1(recursive)

木の探索順序

木を探索する際の順序として以下の図ように

• Inorder(左→根→右)
• Preorder(根→左→右)
• Postorder(左→右→根)

があります

ノードが5つの木の場合を図示すると以下の通りです

Inorderに木を走査する際は

• 基底は現在のノードがNULL(葉の次についているノード)であるときに終了する
• 現在のノードがNULLでないときは左部分木に進み, 現在のノードの値をansに入れる, 右部分木に進むということを繰り返します
  • これによって左の部分木のノードが先に入り, 次に右の部分木のノードが入ります

計算量

ノードを$n$とします

このとき最悪木の深さは$O(n)$であり, 平均では$O(\log(n))$となります

• 空間計算量
  • 最悪は$O(n)$で平均は$O(\log (n))$
• 時間計算量
  • 最悪は$O(n)$で平均は$O(\log (n))$

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
      ans = []
      def helper(node, ans):
        if not node:
          return
        helper(node.left, ans)
        ans.append(node.val)
        helper(node.right, ans)
      helper(root, ans)
      return ans

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    helper(root, ans);
    return ans;
  }
private:
  void helper(TreeNode* node, vector<int>& ans) {
    if (!node) {
      return;
    }
    helper(node->left, ans);
    ans.push_back(node->val);
    helper(node->right, ans);
  }
};

解法2(iterative)

上の解答をStackというデータ構造を使って書き換えます

StackにはLIFOと呼ばれるデータ構造で最後に入れたデータを最初に取り出します

• ここでは現在のノードを入れ, 次に現在のノードの左の子を入れます
• そして, 左の子がいなくなったらStackに入っているノードから取り出したノード(最後に入れたノードから)の値を取り出し, 答えの配列に追加します
• そして, 先頭の次のノードを現在のノードとします
• このノードの右の子を現在のノードとします

これによって, 左の子→ノード→右の子という順番で答えの配列に値が入ります

計算量

計算量は同じです

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
      ans, stack = [], []
      cur = root
      while cur or stack:
        while cur:
          stack.append(cur)
          cur = cur.left
        cur = stack.pop()
        ans.append(cur.val)
        cur = cur.right
      return ans

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    while (stk.size() || cur) {
      while (cur) {
        stk.push(cur);
        cur = cur->left;
      }
      cur = stk.top();
      stk.pop();
      ans.push_back(cur->val);
      cur = cur->right;
    }
    return ans;
  }
};