> For the complete documentation index, see [llms.txt](https://liuyang89116.gitbook.io/my-leetcode-book/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuyang89116.gitbook.io/my-leetcode-book/chapter-4-dfs--bfs/summary_1_dfs_template.md).

# Summary 1: DFS Template

## Template 1: Traverse

其实本质上也是一种分治递归

```java
/*
    Template 1: Traverse
*/

public class Solution {
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // do something with root
        traverse(root.left);
        // do something with root
        traverse(root.right);
    }
}
```

## Template 2: Divide and Conquer

```java
/*
    Template 2: Divide and Conquer
*/

public class Solution {
    public ResultType traverse(TreeNode root) {
        if (root == null) {
            //do something and return;
            //return condition
        }

        //divide
        ResultType left = traverse(root.left);
        ResultType right = traverse(root.right);
        //conquer
        ResultType result = Merge from left and right;
        return result;
    }
}
```