Depth First Search - Githubissues

xiedaxia1hao commented 3 years ago

112. Path Sum 113. Path Sum II 437. Path Sum III 129. Sum Root to Leaf Numbers 543. Diameter of Binary Tree 124. Binary Tree Maximum Path Sum 1430. Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree Grokking. Path With Given Sequence

除了BFS，我们还会使用DFS来遍历树。

通常情况下，我们会用recursion的手段来进行遍历，但是我们也可以通过维护一个stack来进行迭代式的DFS遍历。因为是深度优先遍历，时间复杂度会为O(h)，h代表树的最长高度。

一般情况下，如果题目让我们找root-to-leaf path，我们可以优先使用DFS来做。

DFS的题可以做到现在觉得可以分为两类：

让我们寻找root-to-leaf path
让我们寻找不一定经过root的path

这两种类型的提醒在这个section里都会涉及到，思维方式要稍微reframe一下才行，第一次不太好想到。

xiedaxia1hao commented 3 years ago

DFS模版

112. Path Sum

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。

因为这题是让我们查找根到叶子的路径，所以我们可以考虑用dfs来做。

要做到通过递归的手段来遍历树，我们可以在每一步先从根节点出发，然后同时向根节点的左右子节点来进行递归。

该题的解题步骤可以概括成如下几步：

先从根节点出发进行dfs
如果当前的节点不是leaf node，我们可以做以下几件事情：
- 将targetSum的值减去当前node的值，i.e., targetSum = targetSum - root.val;
- 对该node的左右子节点调用递归函数
在每一步的调用中，我们都要去看是否当前的node是叶子结点，以及是否该node的值等于我们的targetSum。如果both都是true，我们就发现了一条从root到leaf的路径，return true。
如果当前的node是叶子结点，但是node的值和targetSum的值不一样，则return false。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return false;
        }

        // if the current node is a leaf and its value is equal to the sum, we've found a path
        if(root.left == null && root.right == null && targetSum == root.val) {
            return true;
        }

        // recursively call to traverse the left and right sub-tree
        // return true if any of the two recursive call return true
        return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val);
    }
}

这题在leetcode上会有一道follow up，让我们解所有满足条件的path并return。

113. Path Sum II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

这题和刚刚的题目其实是一样的，只是有两个不同点。

每次当我们找到一个root-to-leaf的path的时候，我们会把该path上的节点都保存到一个list中。
我们会遍历所有的path，并且在找到第一个valid path之后仍会继续遍历。

这题的思路其实和backtracking的思路是一致的了，即：

make a change
recurse
undo the change

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> allPaths = new ArrayList<>();
        findPathDFS(root, targetSum, new ArrayList<>(), allPaths);
        return allPaths;
    }
    public void findPathDFS(TreeNode root, int targetSum, List<Integer> currPath, List<List<Integer>> allPaths) {

        if(root == null) {
            return;
        }

        currPath.add(root.val);

        if(root.left == null && root.right == null && root.val == targetSum) {
            allPaths.add(new ArrayList<>(currPath));
        } else {
            findPathDFS(root.left, targetSum-root.val, currPath, allPaths);
            findPathDFS(root.right, targetSum-root.val, currPath, allPaths);
        }

        currPath.remove(currPath.size()-1);

    }
}

437. Path Sum III

给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

这题算是前两题的follow up，因为这题让我们找的不是root-to-leaf的path了，而是任意的从上到下的一条path。那么该如何处理这道题的思路呢？

Grokking里给的办法是，当我们每次把新的node加入到我们的list里面之后，我们遍历当前的list，每当我们找到一个sub-list的和为targetSum的时候，我们就pathCount++。

但是这个方法造成的问题是，我们最差会有O(n2)的时间复杂度。因为我们不仅要遍历n个node，还要对于每个node，我们还要遍历该node之前的所有node，如果是一个skewed tree的话，那就会造成O(n2)的复杂度，如果是完全平衡树，那就是O(nlgn)。

空间复杂度最差情况始终为O(n)，即当该树是个skewed tree的时候的总node数。

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        return findPaths(root, targetSum, new ArrayList<>());
    }

    public int findPaths(TreeNode root, int targetSum, List<Integer> currentPath) {
        if(root == null) {
            return 0;
        }

        currentPath.add(root.val);

        int pathCount = 0, pathSum = 0;

        for(int i = currentPath.size()-1; i >= 0; i--) {
            pathSum += currentPath.get(i);
            if(pathSum == targetSum) {
                pathCount++;
            }
        }

        pathCount += findPaths(root.left, targetSum, currentPath);
        pathCount += findPaths(root.right, targetSum, currentPath);

        currentPath.remove(currentPath.size()-1);

        return pathCount;
    }
}

既然这个解法不是特别的好，我们应该如何优化呢？

这里我们介绍一个prefixSum的概念，用这个解法，可以把时间复杂度降低到O(n)。

这里引用leetcode里一个评论的原文：

The prefix stores the sum from the root to the current node in the recursion

The map stores <prefix sum, frequency> pairs before getting to the current node. We can imagine a path from the root to the current node. The sum from any node in the middle of the path to the current node = the difference between the sum from the root to the current node and the prefix sum of the node in the middle.

We are looking for some consecutive nodes that sum up to the given target value, which means the difference discussed in 2. should equal to the target value. In addition, we need to know how many differences are equal to the target value.

Here comes the map. The map stores the frequency of all possible sum in the path to the current node. If the difference between the current sum and the target value exists in the map, there must exist a node in the middle of the path, such that from this node to the current node, the sum is equal to the target value.

Note that there might be multiple nodes in the middle that satisfy what is discussed in 4. The frequency in the map is used to help with this.

Therefore, in each recursion, the map stores all information we need to calculate the number of ranges that sum up to target. Note that each range starts from a middle node, ended by the current node.

To get the total number of path count, we add up the number of valid paths ended by EACH node in the tree.

Each recursion returns the total count of valid paths in the subtree rooted at the current node. And this sum can be divided into three parts:

the total number of valid paths in the subtree rooted at the current node's left child

the total number of valid paths in the subtree rooted at the current node's right child

the number of valid paths ended by the current node

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
        return findPaths(root, 0, targetSum, preSum);
    }

    public int findPaths(TreeNode root, int currSum, int targetSum, Map<Integer, Integer> preSum) {
        if(root == null) {
            return 0;
        }

        // update the prefix sum by adding the current val
        currSum += root.val;

        // get the number of valid path, ended by the current node
        int numPathToCurr = preSum.getOrDefault(currSum-targetSum, 0);

        // update the map with the current sum, so the map is good to be passed to the next recursion
        preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);

        // add the 3 parts discussed in 8. together
        int res = numPathToCurr + findPaths(root.left, currSum, targetSum, preSum) + findPaths(root.right, currSum, targetSum, preSum);

        // restore the map, as the recursion goes from the bottom to the top
        preSum.put(currSum, preSum.get(currSum)-1);        

        return res;
    }
}

129. Sum Root to Leaf Numbers

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。计算从根节点到叶节点生成的所有数字之和。

这题和前面几题的套路基本是一样的，只是我们要想办法去track当前路径所代表的数字，使用currValue = currValue * 10 + root.val即可。

class Solution {
    public int sumNumbers(TreeNode root) {
        return pathSum(root, 0);
    }

    public int pathSum(TreeNode root, int currValue) {
        if(root == null) {
            return 0;
        }

        currValue = currValue * 10 + root.val;

        if(root.left == null && root.right == null) {
            return currValue;
        } else {
            return pathSum(root.left, currValue) + pathSum(root.right, currValue);
        }

    }
}

Grokking和leetcode里都有一道类似的题，如下：

1430. Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

Grokking. Path With Given Sequence

Given a binary tree and a number sequence, find if the sequence is present as a root-to-leaf path in the given tree.

class PathWithGivenSequence {
  public static boolean findPath(TreeNode root, int[] sequence) {
    if (root == null)
      return sequence.length == 0;

    return findPathRecursive(root, sequence, 0);
  }

  private static boolean findPathRecursive(TreeNode currentNode, int[] sequence, int sequenceIndex) {

    if (currentNode == null)
      return false;

    if (sequenceIndex >= sequence.length || currentNode.val != sequence[sequenceIndex])
      return false;

    // if the current node is a leaf, add it is the end of the sequence, we have found a path!
    if (currentNode.left == null && currentNode.right == null && sequenceIndex == sequence.length - 1)
      return true;

    // recursively call to traverse the left and right sub-tree
    // return true if any of the two recusrive call return true
    return findPathRecursive(currentNode.left, sequence, sequenceIndex + 1)
        || findPathRecursive(currentNode.right, sequence, sequenceIndex + 1);
  }
}

xiedaxia1hao commented 3 years ago

543. Diameter of Binary Tree

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

这题初看可能会摸不着头脑，因为同样的，该题的解并不一定会通过root，正常的dfs在这里可能没有办法适用。但是其实只要我们重新reframe our mind，我们就能比较快的知道这题的解法了。

一个该树最大的周长，其实就是等于某个node它的左子树的最大高度加上右子树的最大高度再加1。我们可以用dfs分别求得左子树的高度，再求得右子树的高度，然后加上1后和一个全局变量max进行比较，如果比当前max大，则更新全局max值。这样当我们遍历完整个树的时候，我们也找到了相应的最大max值。

时间复杂度：O(n)，因为我们只需要遍历所有node一次。空间复杂度：O(n)，最差的情况是该树为一个linkedlist的时候，recursion stack需要O(n)的空间。

class Solution {

    int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        // This will find the max depth going through each node,
        // and update the global maximum to the class member 'max'
        calculateDiameter(root);
        return maxDiameter;
    }

    public int calculateDiameter(TreeNode root) {
        if(root == null) {
            return 0;
        }

        // Find height of left and right subTrees
        int leftTreeHeight = calculateDiameter(root.left);
        int rightTreeHeight = calculateDiameter(root.right);

        // New global max is either already reached,
        // or is acheived using this node as the root
        int currentDiameter = leftTreeHeight + rightTreeHeight;
        maxDiameter = Math.max(maxDiameter, currentDiameter);

        // Return height of tree rooted at this node
        return Math.max(leftTreeHeight, rightTreeHeight) + 1;
    }
}

leetcode里还有一题和该题十分类似：

124. Binary Tree Maximum Path Sum

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
路径和是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其最大路径和。

和上面一题不一样的是，该题让我们求的是最大路径和的path，也是不一定会经过root。但是了解了上面一题的思路之后，这一道题也迎刃而解了。唯一需要注意的是，因为该树是存在负数的node的，所以一些路径和是负数的path，我们需要忽略掉（不然会影响我们的global max值）。

时间复杂度：O(n)，因为我们只需要遍历所有node一次。空间复杂度：O(n)，最差的情况是该树为一个linkedlist的时候，recursion stack需要O(n)的空间。

class Solution {
    int globalMaxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        findMaxPathSum(root);
        return globalMaxSum;
    }

    public int findMaxPathSum(TreeNode root) {
        if(root == null) {
            return 0;
        }

        // ignore paths with negative sums, 
        // since we need to find the maximum sum we should ignore any path which has an overall negative sum.
        int leftSubtreeMaxSum = Math.max(0, findMaxPathSum(root.left));
        int rightSubtreeMaxSum = Math.max(0, findMaxPathSum(root.right));

        // maximum path sum at the current node will be equal to the sum from the left subtree +
        // the sum from right subtree + val of current node
        int lovalMaxSum = leftSubtreeMaxSum + rightSubtreeMaxSum + root.val;

        // update the global maximum sum
        globalMaxSum = Math.max(globalMaxSum, lovalMaxSum);

        // maximum sum of any path from the current node will be equal to the maximum of 
        // the sums from left or right subtrees plus the value of the current node
        return Math.max(leftSubtreeMaxSum, rightSubtreeMaxSum) + root.val;
    }
}

xiedaxia1hao / leetcode_pattern

Depth First Search #20

DFS模版