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

頭尾頭尾打印


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/tree/366.-find-leaves-of-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.