C++, Java and Python Solutions (DFS via Recursion)


  • 0
    P

    Intuition
    It doesn't really matter how you traverse the tree, so long as you keep track of your current depth and hit all left children before their right siblings.

    Then, you can simply construct the returned list in place, by adding values directly to the sublist for your current level.

    C++ (DFS via Recursion)

    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> ret;
            levelOrderImpl(root, ret, 0);
            return ret;
        }
    private:
        void levelOrderImpl(TreeNode* root, vector<vector<int>>& ret, int level) {
            if (!root) return;
            if (level >= ret.size()) {
                ret.push_back({});
            }
            ret.at(level).push_back(root->val);
            levelOrderImpl(root->left, ret, level+1);
            levelOrderImpl(root->right, ret, level+1);
        }
    };
    

    Java (DFS via Recursion)

    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            if (root == null) return Collections.emptyList();
            List<List<Integer>> ret = new ArrayList<>();
            levelOrderImpl(root, ret, 0);
            return ret;
        }
    
        private void levelOrderImpl(TreeNode root, List<List<Integer>> ret, int level) {
            if (root == null) return;
            if (level >= ret.size()) {
                ret.add(new ArrayList<Integer>());
            }
            ret.get(level).add(root.val);
            levelOrderImpl(root.left, ret, level+1);
            levelOrderImpl(root.right, ret, level+1);
        }
    }
    

    Python (DFS via Recursion)

    class Solution(object):
        def levelOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            if not root: return []
            ret = [[]]
            self.levelOrderImpl(root, ret, 0)
            return ret
    
        def levelOrderImpl(self, root, ret, level):
            """
            :type root: TreeNode
            :type ret: List[List[int]]
            :type level: integer
            :rtype: None
            """
            if not root: return
            if len(ret) < level+1:
                ret.append([root.val])
            else:
                ret[level].append(root.val)
            self.levelOrderImpl(root.left, ret, level+1)
            self.levelOrderImpl(root.right, ret, level+1)
    

    Complexity Analysis

    • Time Complexity: O(n), where n is the number of nodes in the tree. This should be clear from the fact that each node is examined exactly once.
    • Space Complexity:
      • If BFS, O(w), where w is the maximum width of the tree, in the queue
      • If DFS, O(d), where d is the maximum depth of the tree, either in the recursion stack or your own stack.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.