All paths of binary tree

Given a binary tree, return all the paths from the root node to the leaf node.

Note: leaf nodes refer to nodes without child nodes.

1. Method 1: the temporary path is stored in String

class Solution {
    List<String> res = new ArrayList<String>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null){
            return res;
        }
        // String init = "";
        // dfs(root, init);   // The above two lines are ok
        dfs(root, "");
        return res;

    }
    public void dfs(TreeNode root,String s) {
    //public void dfs(TreeNode root , Strng s){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            //String temps = new String(root.val);
            s = s+root.val;  // ok
            //s = s + String.valueOf(root.val);  ok
            //res.add(new String(s));      ok
            res.add(s);   //String ok here or not
        }
        s = s + root.val;
        s = s+ "->";
        dfs(root.left, s); // s is a String type, which will be changed by operation on the left side, for example
        dfs(root.right,s);
    }
}

2. Wrong method 2: use StringBuffer to store the temporary path

If we paste the code in method 1 directly, and then change all the places of String to StringBuffer, we will find that the answer is incorrect.

To understand the cause of the error: let's first understand the difference between StringBuffer and String:

1) The String class is immutable, and its object is a constant that cannot be changed. StringBuffer is a variable class, and its objects can be expanded and modified.

2) The modification of an existing String object is to recreate a new object, and then assign the address of the new object to the original reference.

3) StringBuffer is a variable object. When modifying it, it will not recreate the object like String.

After knowing the above differences, let's explain why the code in method 1 above can use String instead of StringBuffer.

Focus on these lines of code:

s = s+ root.val; (for example, "qwer" is currently stored)

dfs(root.left, s);

dfs(root.right,s);

Our code logic is: traverse the currently stored "qwer" to the left subtree and the currently stored "qwer" to the right subtree.

Because our String is modified every time, for example, s = S + root Val, creating a new object,

Therefore, after s="qwer" enters the left subtree, the original s="qwer" will not change, but a new s will be generated, so the original "qwer"

It will still enter the right subtree with the value of "qwer".

When we use StringBuffer, which is a variable object. After the original s="qwer" enters the left subtree, the logic in the left subtree will change the value of the original s.

So the s entering the right subtree is no longer "qwer". Therefore, the result of the left subtree is certainly not in line with our logic.

3. Correct method 2: use StringBuffer to store.

But we can backup s = "qwer" in advance_ Copy, let s = "qwer" enter the left subtree,

Let s_copy = "qwer" enter the right subtree, so it can conform to the overall logic

class Solution {
    List<String> res = new ArrayList<String>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null) return res;
        dfs(root,new StringBuffer());
        return res;
    }
    public void dfs(TreeNode root , StringBuffer s){
        if(root == null) return;
        if(root.left == null && root.right == null){
            s.append(root.val);
            res.add(s.toString());
        }
        s.append(root.val);
        s.append("->");
        StringBuffer s_copy = new StringBuffer(s);
        dfs(root.left , s);
        dfs(root.right, s_copy);
    }
}

Core sentence Code: StringBuffer s_copy = new StringBuffer(s); Note that you must use the new StringBuffer() method to generate objects, which cannot be used directly

Using StringBuffer s_copy = s this method, because this method still does not produce new objects, it will still make errors.

4. Summary and supplement

1) With the help of this example, we can know whether to innovate a new object and the impact of creating a new object on the code logic

Have a good understanding. It used to stay at the level of text concept, but now it has deepened to the level of understanding and application.

2) In the binary tree, we often use String for traversing the tree, but in the backtracking part, we use StringBuffer more

We should analyze specific problems, form muscle memory on the basis of understanding, don't be confused, and try to think from the bottom of logic.