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

Question: Given a BST. Print leaf nodes of the tree in following order: 1st, nth, 2nd, (n-1)th, 3rd,........ Example: Input: 5 / \ 3 8 / \ / \ 1 4 6 9 Outut: 1, 9, 4, 6

頭尾頭尾打印