Tree DFS

自顶而下

  • 是否需要双重递归(即调用根节点的dfs函数后，继续调用根节点的左右节点的pathsum函数): 看题目是从根节点开始，还是从任意节点开始。
  • 是否需要return： 取决于题目是否要求找到叶子节点满足条件的路径，如果是必须到叶节点，就要return。
  • 是否需要回溯: 大部分二叉树不需要，因为dfs(root.left) 和 dfs(root.right) 已经把可能的路径穷尽了。

一般路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
List<List<Integer>> res;
public void dfs(TreeNode root, List<Integer> path){
    //recursion stop condition
    if(root == null)
       return;
   path.add(root.val);
   if(root.left == null && root.right == null){
       //collect the data 
       res.add(papth);
       return;
   }
   //recursion 
   dfs(root.left,path);
   dfs(root.right,path);
}

给定和的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
List<List<Integer>> res;
public void dfs(TreeNode root, int sum, List<Integer> path){
    //recursion stop condition
    if(root == null)
       return;
    sum -= root.val;
    path.add(root.val);
    if(root.left == null && root.right == null && sum == 0){
        //collect the data
        res.add(path);
        return;
    }
    //recursion
    dfs(root.left,sum,path);
    dfs(root.right,sum,path);
}

LeetCode 题目：

非自顶而下

  • left 和 right 要根据题目要求所设置，比如最长路径，最大路径和等等。
  • 全局变量max的初始值设置成0还是 Integer.MIN_VALUE 看题目节点是否存在负值，如果存在就是 Integer.MIN_VALUE ，否则就是0
  • 两点之间路径是1，所以一个点是不能构成路径。
1
2
3
4
5
6
7
8
9
int max = 0;
public int maxPath(TreeNode root){ //以root为路径起始点的最长路径
    if(root == null)
        return 0;
    int left = maxPath(root.left);
    int right = maxPath(root.right);
    max = Math.max(max,left + right);
    return Math.max(left,right) + 1; 
}

Leetcode 题目: