DFS

563.二叉树的深度
image.png

  1. class Solution {
  2.     private int sum;
  4.     public int findTilt(TreeNode root) {
  5.         sum = 0;
  6.         dfs(root);
  7.         return sum;
  8.     }
  10.     private int dfs(TreeNode root){
  11.         if (root == null) return 0;
  12.         int ls = dfs(root.left);
  13.         int rs = dfs(root.right);
  14.         int ss = Math.abs(ls - rs);
  15.         sum += ss;
  16.         return ls + rs + root.val;
  17.     }
  18. }

上面的代码是标准的DFS模板，对应数据结果是tree，如果是数组的话，left和right相当于数组的index。
对于递归代码，我们着重要考虑两点：

  1. 首先要定义好递归函数的定义
  2. 确定递归函数的退出条件，往往是答案找到或数据越界的情况

如上面该题中的dfs函数，其返回值定义为以root为根节点的整棵树的节点之和，因此我们自然而然就能得出该树的坡度=|dfs(left) - dfs(right)|，然后对每个节点的坡度进行累加即可得到结果
对于上题的退出条件很简单，即数据越界，树为空的情况。

回溯

90. 子集II
image.png

  1. class Solution {
  2.     // 转换为相同元素选几次，如[1,1,1]，如果选一个1，选第一个1和第三个1，结果是重复的
  3.     // 所以转为选几个1，如1个1 -> 1 , 2个1-> 1,1 , 3个1 -> 1,1,1
  4.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  5.         Arrays.sort(nums);
  6.         List<List<Integer>> ans = new ArrayList<>();
  7.         List<Integer> cur = new ArrayList<>();
  8.         dfs(nums,0,ans,cur);
  9.         return ans;
  10.     }
  12.     private void dfs(int[] nums , int index, List<List<Integer>> ans, List<Integer> cur){
  13.         int n = nums.length;
  14.         if (index == n){
  15.             ans.add(new ArrayList<>(cur));
  16.             return;
  17.         }
  18.         // 找相同元素范围,last是下一个不同元素位置
  19.         int currentNum = nums[index];
  20.         int last = index;
  21.         while (last < n && nums[last] == currentNum){
  22.             last++;
  23.         }
  25.         // 当前元素不选
  26.         dfs(nums,last,ans,cur);
  28.         // 当前元素选
  29.         for (int i = index; i < last; i++) {
  30.             cur.add(currentNum);
  31.             // 注意dfs的位置是last，代表当前元素选了i次
  32.             dfs(nums,last,ans,cur);
  33.         }
  35.         // 回溯当前元素选择，上面从index到last递增dfs了一遍，到这里肯定里面有last-index个当前元素，全部撤回
  36.         for (int i = index; i < last; i++) {
  37.             cur.remove(cur.size()-1);
  38.         }
  39.     }
  40. }

上面的代码是标准的回溯+DFS的模板代码。
一般对于回溯而言，每个DFS函数中都会有多个情况候选，因此需要对这些候选方案进行遍历，对每个子情况进行选择/不选择，注意遍历一个子情况就代表当前位置已经有了抉择，要进行递归下一轮DFS决定后面index的抉择，如果当前有选择子情况，递归回来后还要删除当前选择的子情况，继续对下个子情况进行相同方式的抉择。

一定要谨记每个DFS函数只对自己当前的index的情况进行遍历，后面递归的情况无需考虑，注意思维的抽象，选择之后进行回退删除。