LeetCode94. Binary Tree Inorder Traversal(Easy)

當談論樹的探索方式時，針對二叉樹有以下三種尋訪方式

以下面的例子來看，數字表示樹節點的值。

    1

   / \

  2   3

 / \

4   5

https://s3.amazonaws.com/issac-ghost/2019/03/preorder-traversal.gif

前序遍歷（Preorder Traversal）：按照根節點 -> 左子樹 -> 右子樹的順序遍歷。

結果：1 -> 2 -> 4 -> 5 -> 3

https://s3.amazonaws.com/issac-ghost/2019/03/inorder-traversal.gif

中序遍歷（Inorder Traversal）：按照左子樹 -> 根節點 -> 右子樹的順序遍歷。

結果：4 -> 2 -> 5 -> 1 -> 3

https://s3.amazonaws.com/issac-ghost/2019/03/postorder-traversal.gif

後序遍歷（Postorder Traversal）：按照左子樹 -> 右子樹 -> 根節點的順序遍歷。

結果：4 -> 5 -> 2 -> 3 -> 1

Inorder 中序遍歷:先走訪左子樹，再走訪父節點，再走訪右子樹。從一棵 tree 的 root 開始，只要 root 的左邊還有 node 就代表還有左子樹可以走訪，接著把左邊的 node 當成 root 再看其左邊是否還有子樹，若有則繼續往左走訪直到左邊沒有 node 為止。

Input: [1,null,2,3]
   1
    \
     2
    /
   3Output: [1,3,2]

遞迴 (recursive)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public: void traversal(TreeNode *node, vector<int> &res) { if (node) { traversal(node->left, res); res.push_back(node->val); traversal(node->right, res); } } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; traversal(root, res); return res; } };

疊代 (iterative)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; TreeNode *cur; while (root || !st.empty()) { while (root) { // 走訪左子樹 st.push(root); // 紀錄父節點 root = root->left; } cur = st.top(); // 回到父節點 st.pop(); res.push_back(cur->val); // 走訪父節點 root = cur->right; // 走訪右子樹 } return res; } };

Ref:

https://www.issacc.com/binary-tree-traversal-preorder-inorder-postorder/

https://www.nku.edu/~longa/classes/mat385_resources/docs/traversal.htm

https://clay-atlas.com/blog/2022/11/20/leetcode-94-binary-tree-inorder-traveral/

https://hackmd.io/@Ji0m0/B1dUOaRjN/https%3A%2F%2Fhackmd.io%2F%40Ji0m0%2FHyAgG6bU_

https://github.com/azl397985856/leetcode/blob/master/problems/94.binary-tree-inorder-traversal.md