366. Find Leaves of Binary Tree

T: O(n)
S: O(n)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }
    private int dfs(TreeNode root, List<List<Integer>> res) {
        if (root == null) {
            return -1;
        }
        int left = dfs(root.left, res);
        int right = dfs(root.right, res);
        int level = Math.max(left, right) + 1;
        
        if (res.size() == level) {
            res.add(new ArrayList<>());
        }
        res.get(level).add(root.val);
        return level;
    }
}

/*

   0      1.  2
[[4,5,3],[2],[1]]


so leaf is 0,

T: O(n)
S: O(n)
*/

if we really want to delete nodes


class Solution {
    TreeNode rootNode;
    public List<List<Integer>> findLeaves(TreeNode root) {
        rootNode = root;
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }
    private int dfs(TreeNode node, List<List<Integer>> res) {
        if (node == null) {
            return -1;
        }
        int left = dfs(node.left, res);
        int right = dfs(node.right, res);
        int level = Math.max(left, right) + 1;
        
        if (res.size() == level) {
            res.add(new ArrayList<>());
        }
        res.get(level).add(node.val);
        
        node.left = null;  // do this
        node.right = null; // do this
        //System.out.println("delete node.val:" + node.val);
        //dfs(rootNode);
        
        return level;
    }
    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node.val);
        dfs(node.left);
        dfs(node.right);
    }
}

/*
count level from leaf
leaf node => 0
leaf node => 1
leaf node => 2

so we need to cal height => dfs traverse to 
level 0 = height - 1
dfs, then when the height is 1 (we seem it as level 0), start to add node to level 0, res index 0

when the height is 2 (we seem it as level 1), start to add node to level 1, res index 1

when the height is 3 (we seem it as level 2), start to add node to level 2, res index 2
*/

给一个树每次删除其叶节点层的节点，直到删完，打印其删除路径，例如：5,4,2,3,1
Follow up 1：删完一个叶节点之后，规定下一步不能删除其母节点，只能删其他的叶节点，打印其删除路径,  
例如：5,3
Follow up 2： 先删除所有的叶节点，再删除新产生的叶节点，打印其删除路径，例如：5,3,4,2,1
           1
          /  \
        2    3
      /     
   4      
  /
5

just postorder

        int left = dfs(node.left, res);
        int right = dfs(node.right, res);
        
        print(node.val)

2.

  1. use 

    private void dfs(TreeNode node) {
    if (node == null) {
        return;
    }
    dfs(node.left);
    dfs(node.right);
    if (node.left == null && node.right == null) {
        System.out.println(node.val);
    }
}

or just use level

private int dfs(TreeNode node, List<List<Integer>> res) {
        if (node == null) {
            return -1;
        }
        int left = dfs(node.left, res);
        int right = dfs(node.right, res);
        int level = Math.max(left, right) + 1;
        
        if (level == 0) {
            res.add(node.val);
        }
        if (level == 1) {
            node.left = null;  // do this
            node.right = null; // do this
        }

3.

it's this question

頭尾頭尾打印

Previous652. Find Duplicate SubtreesNext606. Construct String from Binary Tree

Last updated