> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/tree/366.-find-leaves-of-binary-tree.md).

# 366. Find Leaves of Binary Tree

```
T: O(n)
S: O(n)
```

```java
/**
 * 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

```java

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&#x20;

   ```
   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

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

頭尾頭尾打印