Leetcode102. Binary Tree Level Order Traversal

給定一個二叉樹，返回所有節點值的層序遍歷結果。（從左到右，從上到下遍歷）

Python

方法一 : BFS

class Solution(object):
    def levelOrder(self, root):

        if not root: return []
        q  = [root]
        result = []
        while q:
            L = len(q)
            level = []
            for i in range(L):
                node = q.pop(0)
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            result.append(level)
        return result

方法二 : DFS

class Solution(object):
    def levelOrder(self, root):
        ret = [ ]
        self.helper(root, 0, ret)
        return ret         
        
    def helper(self, root, level, ret):
        if root:
            if len(ret) < level+1:
                ret.append([ ]) 
            ret[level].append(root.val)
            self.helper(root.left,  level+1, ret)   
            self.helper(root.right, level+1, ret)

C++

方法一 : BFS

首先將根節點加入隊列中。然後進入循環，該循環會一直執行直到隊列為空。在每一次循環中，先記錄當前隊列的大小，然後遍歷這個大小的所有元素，將這些元素的值加入當前層的結果中。同時，將這些元素的左右子節點加入隊列中，以便後續的遍歷。最後，將當前層的結果加入結果集中，並重複上述步驟，直到隊列為空。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) {
            return res;
        }

        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.push_back(level);
        }
        return res;
    }
};

方法二 : DFS

定義一個函數，該函數需要傳入當前節點、當前層數以及結果集。在函數中，如果當前節點為空，直接返回；否則，首先檢查結果集的大小是否大於等於當前層數，如果不是，則說明當前層還沒有被添加到結果集中，因此需要添加一個空的數組，表示當前層的結果。然後，我們將當前節點的值添加到當前層的結果中，並分別遞歸遍歷當前節點的左右子節點，層數加一，同時將結果集作為參數傳遞給子函數。最後，遞歸結束後，可以得到完整的層序遍歷結果。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        levelOrderHelper(root, 0, res);
        return res;
    }

private:
    void levelOrderHelper(TreeNode* node, int level, vector<vector<int>>& res) {
        if (node == nullptr) {
            return;
        }
        if (res.size() <= level) {
            res.push_back({});
        }
        res[level].push_back(node->val);
        levelOrderHelper(node->left, level + 1, res);
        levelOrderHelper(node->right, level + 1, res);
    }
};

Python

C++

相關