Last Updated on 2022-11-20 by Clay
題目
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]
Example 2:
Input: root = [] Output: []
Example 3:
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?
樹的遍歷大致上可以分為四種：
- Preorder 前序遍歷
- Inorder 中序遍歷
- Postorder 後序遍歷
- level-order（不確定該如何翻譯，但就是 BFS 一層層遍歷下去）
而本題就是經典的中序（Inorder）遍歷。
解題思路
我並不懂為什麼 Follow up 要求要用迭代法，我目前看過跟思考的幾個迭代法感覺既不直覺效能又差。當然，可能是我漏考慮了什麼。
如果我的思考哪邊出了問題，歡迎隨時留言告訴我。
基本上我做遞迴的方法，就是：
- 一直把左節點放入遞迴函式中，一路走到最底
- 把當前節點的值儲存在要返回的陣列中
- 把右節點放入遞迴函示中
這樣就完成中序遍歷了。基本上，我會先儲存最左下邊的節點值，再返回上一層，儲存完當前節點值後再開始探索右節點，儲存完後再回到上上一層...... 依此類推。
C++ 範例程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void inorderVisit(vector<int>& results, TreeNode* root) {
if (root) {
inorderVisit(results, root->left);
results.push_back(root->val);
inorderVisit(results, root->right);
}
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> results;
inorderVisit(results, root);
return results;
}
};Python 範例程式碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderVisit(self, results, root):
if root:
self.inorderVisit(results, root.left)
results.append(root.val)
self.inorderVisit(results, root.right)
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
results = []
self.inorderVisit(results, root);
return results