Binary Tree Inorder Traversal : 給定Binary Tree的根,返回其節點值的Inorder Traversal(中序遍歷)。
- 前序 (preorder): 中 -> 左 -> 右
- 中序 (inorder): 左 -> 中 -> 右。注意:對二元搜尋樹 (binary search tree, BST) 做 inorder traversal 就是由小到大依序遍歷。
- 後序 (postorder): 左 -> 右 -> 中
Python
方法一 : 遞歸
按左子樹->節點->右子樹的順序遍歷
class Solution:
def traversal(self, root: TreeNode, inorder_list: List[int]):
ans=[]
def inorder(root):
if root ==None:
return None
if root.left!=None:
inorder(root.left) #左子樹
ans.append(root.val) #按左子樹->節點->右子樹順序加入
if root.right!=None:
inorder(root.right) #右子樹
inorder(root)
return ans
方法二 : 迭代
先把節點所有的左節點放入棧中,然後開始出棧,每次出棧都把棧中的元素放入到ans中,並且把這個結果的右子樹放入棧中。這裡的遍歷順序會先沿著左方到達最左下角的節點,然後每次彈出來一個節點,把該節點的值放入ans中,並開始處理該節點的右子樹
class Solution:
def traversal(self, root: TreeNode, inorder_list: List[int]):
stack=[]
ans=[]
while True:
while root:
stack.append(root) #把節點所有的左節點放入棧中
root=root.left
if not stack:
return ans
root=stack.pop() #出棧
ans.append(root.val) #每次出棧都把棧中的元素放入到ans中
root=root.right #處理該節點的右子樹
C++
方法一 : 遞歸
定義了一個 inorder 函數,它用來實現遞歸的過程。函數中有兩個參數,第一個是當前節點,第二個是存儲結果的向量。遞歸的結束條件是當前節點為空,這時直接返回即可。遞歸的過程中,首先訪問當前節點的左子樹,然後將當前節點的值添加到結果中,最後再訪問當前節點的右子樹。
時間複雜度:O(n),其中 n 是二叉樹的節點數。每個節點恰好被遍歷一次。
空間複雜度:O(n),需要遞歸調用棧的空間。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
void inorder(TreeNode* root, vector<int>& res) {
if (root == nullptr) {
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
};
方法二 : 迭代
我們先將根節點入棧,然後對於每一個節點,如果其左子樹不為空,則將左子樹入棧,否則將當前節點出棧,並訪問它的值,再將右子樹入棧。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
res.push_back(cur->val);
cur = cur->right;
}
return res;
}
};