Java backtracking O(n) time O(n) space No hashing!


  • 28

    The essential of problem is not to find the leaves, but group leaves of same level together and also to cut the tree. This is the exact role backtracking plays. The helper function returns the level which is the distance from its furthest subtree leaf to root, which helps to identify which group the root belongs to

        public class Solution {
            public List<List<Integer>> findLeaves(TreeNode root) {
                List<List<Integer>> list = new ArrayList<>();
                findLeavesHelper(list, root);
                return list;
            }
            
      // return the level of root
            private int findLeavesHelper(List<List<Integer>> list, TreeNode root) {
                if (root == null) {
                    return -1;
                }
                int leftLevel = findLeavesHelper(list, root.left);
                int rightLevel = findLeavesHelper(list, root.right);
                int level = Math.max(leftLevel, rightLevel) + 1;
                if (list.size() == level) {
                    list.add(new ArrayList<>());
                }
                list.get(level).add(root.val);
                root.left = root.right = null;
                return level;
            }
        }

  • 0
    B

    Thanks sharing!
    I rewrite it in C++.

    class Solution {
    public:
    vector<vector<int>> findLeaves(TreeNode* root) {

    	vector<vector<int> > result;
    	level_helper(root, result);
    	return result;
    
    }	
    
    int level_helper(TreeNode* node, vector<vector<int>> &result){
    
    	if(!node) return -1;
    	int left_level = level_helper(node->left, result);
    	int right_level = level_helper(node->right, result);
    	int level = max(left_level, right_level)+1;
    	
    	if(result.size()==level){
    	    result.push_back({});
    	}
    	
    	result[level].push_back(node->val);
    	node->left = node->right = NULL;
    	
    	return level;
    }
    

    };


  • 0
    J

    I didn't see why the node.left and node.right need to set to null, here is my python version.

      def findLeaves(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            res = []
            self.depth2leaf(res, root)
            return res
    
        def depth2leaf(self, l, root):
            if not root:
                return -1
            left = self.depth2leaf(l, root.left)
            right = self.depth2leaf(l, root.right)
            level = max(left, right) + 1
            if len(l) == level:
                l.append([])
            l[level].append(root.val)
            return level
    
    ···

Log in to reply
 

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