LeetCode 94. Binary Tree Inorder Traversal

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;
    }
};

Python

C++

相關