Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Why DFS

I believe that the friends who have learned data structure know that DFS (depth-first search) is a very important search algorithm, may directly say that you feel not conditional you can go to see some algorithm competition. Every one of these games is going to involve DFS in some way or another, and DFS is probably something we all know about but we all know about it in order to avoid being too arrogant to write about it. In order to avoid this embarrassment we are going to take advantage of this activity for a few days to practice, well we don’t have to talk about fat.

PS: THESE days, I found that some fat friends do not know what DFS is. I’d better say it briefly, otherwise this problem will be difficult to do.

Depth First Search belongs to a graph algorithm, abbreviated as DFS, namely Depth First Search. The process is simply as deep as you can go into every possible branch path, and each node can only be accessed once.

For example, if we initiate A depth-first search from point A (the following access order is not unique, the second point could be either B or C or D), we might get an access process like A->B->E (no path! Backtrace to A)->C->F->H->G->D (no path, finally backtrace to A,A also has no adjacent node not visited, the search ends). The characteristic of depth-first search is briefly explained: the result of depth-first search must be a connected component of graph. Depth-first searches can be initiated from multiple points. If you sort each node by “end time” during a depth-first search (by creating a list, then adding that node to the end of the list if all of its neighbors have been accessed, and then reversing the entire list), Then we can get what is called “topological sort “, i.e. topological sort. [1]

The title

You are given the root node of a binary tree, root, and are given all paths from root to leaf, in any order.

A leaf node is a node that has no children.

Example 1:

Enter: root = [1.2.3.null.5] output: ["1 - > 2 - > 5"."1 - > 3"]
Copy the code

Example 2:

Enter: root = [1] output: ["1"]
Copy the code

To find all paths, you need to determine the number of leaf nodes.

Solution 1: Top-down solution (easier to understand but more space and time consuming)

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    List<String> list=new ArrayList<String>();
    public List<String> road(TreeNode root,StringBuilder s){
          if(root==null)return list;
          if(root.left==null&&root.right==null){
              s.append("- >"+root.val);
              s.delete(0.2);// Remove the initial -> symbol
              list.add(s.toString());
            return list;
        }
        s.append("- >"+root.val);
        if(root.left! =null&&root.right! =null) {// Because new paths can only occur if both the left and right children exist
            StringBuilder s1=new StringBuilder(s);// To avoid a path with a duplicate of the previous path
            StringBuilder s2=new StringBuilder(s);
            road(root.left,s1);
            road(root.right,s2);
        }else{
            road(root.left,s);
            road(root.right,s);
        }
        return list;
    }
    public List<String> binaryTreePaths(TreeNode root) {
        StringBuilder s=new StringBuilder();
        returnroad(root,s); }}Copy the code

Method 2:

The most intuitive way is to use depth-first search. When a depth-first search traverses a binary tree, we need to consider the current node as well as its children.

If the current node is not a leaf node, the node is added at the end of the current path and each child node of the node continues to be recursively traversed. If the current node is a leaf node, add the node at the end of the current path to get a path from the root node to the leaf node. Add the path to the answer. So when we walk through the binary tree we have all the paths from the root node to the leaf node. Of course, depth-first search can also be implemented in a non-recursive way, which I won’t go into here.


class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        constructPaths(root, "", paths);
        return paths;
    }

    public void constructPaths(TreeNode root, String path, List<String> paths) {
        if(root ! =null) {
            StringBuffer pathSB = new StringBuffer(path);
            pathSB.append(Integer.toString(root.val));
            if (root.left == null && root.right == null) {  // The current node is a leaf node
                paths.add(pathSB.toString());  // Add the path to the answer
            } else {
                pathSB.append("- >");  // The current node is not a leaf node, continue recursive traversalconstructPaths(root.left, pathSB.toString(), paths); constructPaths(root.right, pathSB.toString(), paths); }}}}Copy the code