【leetcode】DFS问题

发表于 | 浏览 次
字数统计: 3,561 | 阅读时长 ≈ 17

二叉树的深度优先遍历

DFS是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。

当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

如上图的例子，DFS访问数组为：ABDECFG。

实现方式

分析一下，在遍历了根结点后，就开始遍历左子树，最后才是右子树。

因此可以借助堆栈的数据结构，由于堆栈是后进先出的顺序，由此可以先将右子树压栈，然后再对左子树压栈，

这样一来，左子树结点就存在了栈顶上，因此某结点的左子树能在它的右子树遍历之前被遍历。

递归

思路比较简单，就是从root开始，先将root值加入结果集，然后先对其做左节点递归调用做DFS，然后是对右节点DFS。当遇到空节点时，返回上层。

public class BinaryTreeDFS {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }
    public void DFSRecurtionHelper(TreeNode root,List<Integer> results){
        //遇到空节点，返回
        if (root == null){
            return;
        }
        //root放入results,递归处理左右节点
        results.add(root.val);
        DFSRecurtion(root.left);
        DFSRecurtion(root.right);
    }
    
    public List<Integer> DFSRecurtion(TreeNode root){
        List<Integer> results = new ArrayList<>();
        DFSRecurtionHelper(root,results);
        return results;
    }
}

非递归（栈）

因此可以借助堆栈的数据结构，由于堆栈是后进先出的顺序，由此可以先将右子树压栈，然后再对左子树压栈，这样一来，左子树结点就存在了栈顶上，因此某结点的左子树能在它的右子树遍历之前被遍历。

public List<Integer> DFSwithStack(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> results = new ArrayList<>();
    stack.push(root);
    while (!stack.empty()){
        TreeNode temp = stack.pop();
        results.add(temp.val);
        if(temp.right != null){
            stack.push(temp.right);
        }
        if(temp.left != null){
            stack.push(temp.left);
        }
    }
    return results;
}

leetcode 相关习题

Populating Next Right Pointers in Each Node

题目

Given a binary tree

>     struct TreeLinkNode {
>       TreeLinkNode *left;
>       TreeLinkNode *right;
>       TreeLinkNode *next;
>     }
>
>

>

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

>          1
>        /  \
>       2    3
>      / \  / \
>     4  5  6  7
>
>

>

After calling your function, the tree should look like:

>          1 -> NULL
>        /  \
>       2 -> 3 -> NULL
>      / \  / \
>     4->5->6->7 -> NULL
>

就是将同一层上的节点的next指向右边的节点

分析

tag是DFS，但我一开始想到的是BFS。

  1. BFS：

将每一层节点加入队列，出队列时，左边节点的next指向右边节点。

但DFS会更快一些

  1. DFS：

用DFS的核心思想是对于一个节点来说，将其左孩子的next指向右孩子，其右孩子的next指向其本身next节点的左孩子。

题目要求不能引入额外的空间，所以更应该用dfs的

代码

public class PopulatingNextRightPointersinEachNode {
     public class TreeLinkNode {
         int val;
         TreeLinkNode left, right, next;
         TreeLinkNode(int x) { val = x; }
     }
	//BFS
    public void connect(TreeLinkNode root) {
         if(root == null){
             return;
         }
        Queue<TreeLinkNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int len = queue.size();
            while(len > 0){
                //如果是本层最后一个了，其next指向NULL
                TreeLinkNode temp = queue.poll();
                if(len == 1){
                    temp.next = null;
                }
                //如果不是本层最后一个，其next指向下一个节点
                else {
                    temp.next = queue.peek();
                }
                if(temp.left != null){
                    queue.add(temp.left);
                }
                if(temp.right != null){
                    queue.add(temp.right);
                }
                len--;
            }
        }
    }
  
  //DFS
  public void dfshelper(TreeLinkNode root){
        if(root == null){
            return;
        }
        if(root.left != null && root.right != null){
            root.left.next = root.right;
            if(root.next !=null){
                root.right.next = root.next.left;
            }
            else {
                root.right.next = null;
            }
            dfshelper(root.left);
            dfshelper(root.right);
        }
    }
    //DFS
    public void connectDFS(TreeLinkNode root) {
        if(root == null){
            return;
        }
         root.next = null;
         dfshelper(root);
    }
}

Path Sum

题目

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:

Given the below binary tree and 

> sum = 22
>

>

,

>               5
>              / \
>             4   8
>            /   / \
>           11  13  4
>          /  \      \
>         7    2      1
>
>

>

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

给定二叉树和一个整数sum,返回二叉树中是否存在一条从root到叶子的路径，长度为sum

分析

DFS，分别对节点的左右孩子做DFS，sum需减掉当前节点的值。

当遇到叶子节点，且该点的值==sum时，即找到了一条合法路径，返回true

这里需要注意的是测试样例中有负数的情况，所以不能根据剩余的sum值进行剪枝。

代码

public boolean dfshelper(TreeNode root, int sum){
  //sum == root且root是叶子节点
  if(sum == root.val && root.left == null && root.right == null){
    return true;
  }
  else {
    if(root.left != null) {
      if(dfshelper(root.left, sum - root.val)){
        return true;
      }
    }
    if(root.right != null){
      if(dfshelper(root.right, sum - root.val)){
        return true;
      }
    }
    return false;
  }
}
public boolean hasPathSum(TreeNode root, int sum) {
  if(root == null){
    return false;
  }
  return dfshelper(root,sum);
}

Path Sum II

题目

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:

Given the below binary tree and 

> sum = 22
>

>

>               5
>              / \
>             4   8
>            /   / \
>           11  13  4
>          /  \    / \
>         7    2  5   1
>
>

>

return

> [
>    [5,4,11,2],
>    [5,8,4,5]
> ]
>

分析

跟上一题一样的，这次要把合法路径全都记录下来返回。

代码

public class PathSumII {
    public class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) { val = x;}
    }
    List<Integer> result = new ArrayList<>();
    List<List<Integer>> results = new ArrayList<>();
    public void helper(TreeNode root, int sum) {
        if(root.val == sum && root.left == null && root.right == null){
            result.add(root.val);
            List<Integer> temp = new ArrayList<>();
            temp.addAll(result);
            results.add(temp);
            result.remove(result.size()-1);
        }
        else {
            result.add(root.val);
            if(root.left != null){
                helper(root.left,sum - root.val);
            }
            if(root.right != null){
                helper(root.right,sum - root.val);
            }
            result.remove(result.size()-1);
        }
    }
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root == null){
            return results;
        }
        helper(root,sum);
        return results;
    }
}

Path Sum III

题目

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

> root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
>
>       10
>      /  \
>     5   -3
>    / \    \
>   3   2   11
>  / \   \
> 3  -2   1
>
> Return 3. The paths that sum to 8 are:
>
> 1.  5 -> 3
> 2.  5 -> 2 -> 1
> 3. -3 -> 11
>

跟前面两道的不同是：起止点不一定是root和leaf可以是树中的任意两点

分析

方法一：双层递归

对树中的每一个节点都进行搜索，从该点开始是否有合法路径。

可以转化为，对根节点搜索sum合法路径，然后对根节点的左右节点分别搜索sum合法路径，其中对其左右节点搜索合法路径时，也需要对其自身和其左右节点分别搜索，这是外层递归

搜索路径长度本身又是一层递归，每次减掉当前节点val，这是第二层递归

方法二：前缀长度

计算从root到每一个节点的路径长度，存储在一个hashmap中，key为root到树种节点的路径长度，value为出现次数。

当计算到某一个节点时，从root到该节点的路径长度为len，则以该节点为结尾的合法路径的个数为map中key为sum-len的value值。

注意：每次回退时需要将root到这点的路径长度在hashmap中的value-1。

代码

方法一：双层递归

public class PathSumIII {
    public class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) { val = x;}
    }
    public int helper(TreeNode root, int sum){
        int res = 0;
        if(root == null){
            return 0;
        }
        //如果到当前点已经是合法路径了，res+1
        if(root.val == sum){
            res++;
        }
        //接续沿着左右节点寻找是否还有合法路径
        res += helper(root.left,sum - root.val);
        res += helper(root.right,sum - root.val);
        return res;
    }
    public int pathSum(TreeNode root, int sum) {
        if(root == null){
            return 0;
        }
        //从当前节点开始和为sum 和从左、右节点开始和为sum
        return helper(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
    }
}

方法二：前缀搜索

import java.util.HashMap;
public class PathSumIII {
    public class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) { val = x;}
    }
  
    HashMap<Integer,Integer> map = new HashMap<>();
    public int helper(TreeNode root, int sum,int fromR){
        int res = 0;
        if(root == null){
            return res;
        }
        int temp = fromR + root.val;
        res += map.getOrDefault(temp - sum,0);
        map.put(temp,map.getOrDefault(temp,0)+1);
        res = res + helper(root.left,sum,temp)+helper(root.right,sum,temp);
        map.put(temp,map.get(temp)-1);
        return res;
    }
    public int pathSum(TreeNode root, int sum) {
        if(root == null){
            return 0;
        }
        map.put(0,1);
        //从当前节点开始和为sum 和从左、右节点开始和为sum
        return helper(root,sum,0);
    }
}

Path Sum IV

题目

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

  1. The hundreds digit represents the depth D of this node, 1 <= D <= 4.
  2. The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
  3. The units digit represents the value V of this node, 0 <= V <= 9.

Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.

Example 1:

> Input: [113, 215, 221]
> Output: 12
> Explanation: 
> The tree that the list represents is:
>     3
>    / \
>   5   1
>
> The path sum is (3 + 5) + (3 + 1) = 12.
>
>

>

Example 2:

> Input: [113, 221]
> Output: 4
> Explanation: 
> The tree that the list represents is: 
>     3
>      \
>       1
>
> The path sum is (3 + 1) = 4.
>

以数组的形式给定一棵二叉树，用三位数表示节点，其中百位代表层数，十位代表在某一层中从左到右的位置，各位代表节点数值，计算从root到每一个leaf的路径长度之和。

分析

假设一个几点的百位和十位是xy，则其左孩子和右孩子分别是：

left：(x+1)(2y-1)

right：(x+1)(2y)

可以根据这个性质，将数组中的节点放入hashmap中，key为百位十位，value为节点值。然后在map中寻找左右节点进行DFS，当遍历到叶子节点时，将本条路径长度加入路径长度总和。

代码

int sum;
public int dfs(HashMap<Integer,Integer> map,int root,int res){
  res += map.get(root);
  int left = (root/10+1) * 10 + (root%10)*2-1;
  int right = (root/10+1) * 10 + (root%10)*2;
  //如果左右都没有了路径了，是叶子节点
  if(!map.containsKey(left) && !map.containsKey(right)){
    sum += res;
  }
  //如果左边有路径
  if(map.containsKey(left)){
    dfs(map,left,res);
  }
  //如果右边有路径
  if(map.containsKey(right)){
    dfs(map,right,res);
  }
  res -= map.get(root);
}
public int pathSum(int[] nums) {
  HashMap<Integer,Integer> map = new HashMap<>();
  for(int i = 0 ; i <nums.length;i++){
    map.put(nums[i]/10,nums[i] % 10);
  }
  dfs(map,11,0);
  return sum;
}

Flatten Binary Tree to Linked List

题目

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

>          1
>         / \
>        2   5
>       / \   \
>      3   4   6
>
>

>

The flattened tree should look like:

>    1
>     \
>      2
>       \
>        3
>         \
>          4
>           \
>            5
>             \
>              6
>

将二叉树压到一条右子树上

思路

这道题实际上是要将每个节点左子树的前序遍历插入到右子树前面。

所以我的思路是如果遇到节点root有右子树，就先把右子树存下来，然后dfs处理左子树，当左子树处理完之后，再将右子树插入到左子树。

DSF的时候，把原来的左子树放到节点的右边，然后节点向下移动，递归处理左子树。

代码

public class FlattenBinaryTreetoLinkedList {
    TreeNode temp;//记录当前节点
	public void dfs(TreeNode root){
        if(root.left == null && root.right == null){
            return;
        }
        //如果右节点不空，先把右边节点存下来
        TreeNode right = null;
        if(root.right != null) {
            right = new TreeNode(root.right.val);
            right.left = root.right.left;
            right.right = root.right.right;
        }
        //如果左子树非空，将左子树挪到右边，左子树置为空，temp下移，继续dfs temp的左子树
        if(temp.left != null){
            temp.right = temp.left;
            temp.left = null;
            temp = temp.right;
            dfs(temp);
        }
      //如果右节点非空，将之前记录下来的右子树放到temp右边，然后temp下移，继续dfs
        if(right != null){
            temp.right = right;
            temp = temp.right;
            dfs(temp);
        }
    }
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        temp = root;
        dfs(root);
    }
}

House Robber III

baseline

递归调用，相当于暴力遍历所有情况

public int rob(TreeNode root) {
    if(root == null){
        return 0;
    }
    int sum = 0;
    //如果选择root，则需避开其左右孩子
    if(root.left != null){//选择左边孩子的左右孩子
        sum += rob(root.left.left) + rob(root.left.right);
    }
    if(root.right != null){//选择右边孩子的左右孩子
        sum += rob(root.right.left) + rob (root.right.right);
    }
    //选当前节点和不选当前节点的最大值
    return Math.max(root.val + sum,rob(root.left) + rob(root.right));
}

dp

用hashmap将计算过的每一个节点的max值存储下来，后面再用到直接返回

public class HouseRobberIII {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    HashMap<TreeNode,Integer> map = new HashMap<>();
    public int rob(TreeNode root) {
        if(root == null){
            return 0;
        }
        //如果已经计算过了
        if(map.containsKey(root)){
            return map.get(root);
        }
        int sum = 0;
        //如果选择root，则需避开其左右孩子
        if(root.left != null){//选择左边孩子的左右孩子
            sum += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){//选择右边孩子的左右孩子
            sum += rob(root.right.left) + rob (root.right.right);
        }
        //选当前节点和不选当前节点的最大值
        int maxval =  Math.max(root.val + sum,rob(root.left) + rob(root.right));
        map.put(root,maxval);
        return maxval;
    }
}

优化

递归函数返回一个大小为2的一维数组res，其中res[0]表示不包含当前节点值的最大值，res[1]表示包含当前值的最大值，那么我们在遍历某个节点时，首先对其左右子节点调用递归函数，分别得到包含与不包含左子节点值的最大值，和包含于不包含右子节点值的最大值，那么当前节点的res[0]就是左子节点两种情况的较大值加上右子节点两种情况的较大值，res[1]就是不包含左子节点值的最大值加上不包含右子节点值的最大值，和当前节点值之和，返回即可

public int[] solve(TreeNode root){
    if(root == null){//如果是空节点
        return new int[2];
    }
    int[] left = solve(root.left);//左孩子的res
    int[] right = solve(root.right);//右孩子的res
    int[] res = new int[2];
    //不包含root的情况：左孩子包括和不包括的最大值+右孩子同理
    res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
    //包含root的情况：不包括左孩子和右孩子，需要加上自身value
    res[1] = left[0] + right[0] + root.val;
    return res;
}
public int rob(TreeNode root) {
    int[] res = solve(root);
    return Math.max(res[0],res[1]);
}