<p align="center">
  <a href="https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ"><img src="https://img.shields.io/badge/知识星球-代码随想录-blue" alt=""></a>
  <a href="https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw"><img src="https://img.shields.io/badge/刷题-微信群-green" alt=""></a>
  <a href="https://img-blog.csdnimg.cn/20201210231711160.png"><img src="https://img.shields.io/badge/公众号-代码随想录-brightgreen" alt=""></a>
  <a href="https://space.bilibili.com/525438321"><img src="https://img.shields.io/badge/B站-代码随想录-orange" alt=""></a>
</p>
<p align="center"><strong>欢迎大家参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！</strong></p>


# 二叉树：以为使用了递归，其实还隐藏着回溯

> 补充一波

昨天的总结篇中[还在玩耍的你，该总结啦！（本周小结之二叉树）](https://mp.weixin.qq.com/s/QMBUTYnoaNfsVHlUADEzKg)，有两处问题需要说明一波。

## 求相同的树

[还在玩耍的你，该总结啦！（本周小结之二叉树）](https://mp.weixin.qq.com/s/QMBUTYnoaNfsVHlUADEzKg)中求100.相同的树的代码中，我笔误贴出了 求对称树的代码了，细心的同学应该都发现了。

那么如下我再给出求100. 相同的树 的代码，如下：

```C++
class Solution {
public:
    bool compare(TreeNode* tree1, TreeNode* tree2) {
        if (tree1 == NULL && tree2 != NULL) return false;
        else if (tree1 != NULL && tree2 == NULL) return false;
        else if (tree1 == NULL && tree2 == NULL) return true;
        else if (tree1->val != tree2->val) return false; // 注意这里我没有使用else

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool compareLeft = compare(tree1->left, tree2->left);       // 左子树：左、 右子树：左
        bool compareRight = compare(tree1->right, tree2->right);    // 左子树：右、 右子树：右
        bool isSame = compareLeft && compareRight;                  // 左子树：中、 右子树：中（逻辑处理）
        return isSame;

    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return compare(p, q);
    }
};
```

以上的代码相对于：[二叉树：我对称么？](https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg) 仅仅修改了变量的名字（为了符合判断相同树的语境）和 遍历的顺序。

大家应该会体会到：**认清[判断对称树](https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg)本质之后， 对称树的代码 稍作修改 就可以直接用来AC 100.相同的树。**

## 递归中隐藏着回溯

在[二叉树：找我的所有路径？](https://mp.weixin.qq.com/s/Osw4LQD2xVUnCJ-9jrYxJA)中我强调了本题其实是用到了回溯的，并且给出了第一个版本的代码，把回溯的过程充分的提现了出来。

如下的代码充分的体现出回溯：(257. 二叉树的所有路径)

```C++
class Solution {
private:

    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val);
        // 这才到了叶子节点
        if (cur->left == NULL && cur->right == NULL) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if (cur->left) {
            traversal(cur->left, path, result);
            path.pop_back(); // 回溯
        }
        if (cur->right) {
            traversal(cur->right, path, result);
            path.pop_back(); // 回溯
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};
```


如下为精简之后的递归代码：(257. 二叉树的所有路径)
```
class Solution {
private:
    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左  回溯就隐藏在这里
        if (cur->right) traversal(cur->right, path + "->", result); // 右 回溯就隐藏在这里
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};
```

上面的代码，大家貌似感受不到回溯了，其实**回溯就隐藏在traversal(cur->left, path + "->", result);中的 path + "->"。  每次函数调用完，path依然是没有加上"->" 的，这就是回溯了。**

为了把这份精简代码的回溯过程展现出来，大家可以试一试把：

```
if (cur->left) traversal(cur->left, path + "->", result); // 左  回溯就隐藏在这里
```

改成如下代码：

```
path += "->";
traversal(cur->left, path, result); // 左
```

即：

```

if (cur->left) {
    path += "->";
    traversal(cur->left, path, result); // 左
}
if (cur->right) {
    path += "->";
    traversal(cur->right, path, result); // 右
}
```

此时就没有回溯了，这个代码就是通过不了的了。

如果想把回溯加上，就要 在上面代码的基础上，加上回溯，就可以AC了。

```
if (cur->left) {
    path += "->";
    traversal(cur->left, path, result); // 左
    path.pop_back(); // 回溯
    path.pop_back();
}
if (cur->right) {
    path += "->";
    traversal(cur->right, path, result); // 右
    path.pop_back(); // 回溯
    path.pop_back();
}
```

**大家应该可以感受出来，如果把 `path + "->"`作为函数参数就是可以的，因为并有没有改变path的数值，执行完递归函数之后，path依然是之前的数值（相当于回溯了）**

如果有点遗忘了，建议把这篇[二叉树：找我的所有路径？](https://mp.weixin.qq.com/s/Osw4LQD2xVUnCJ-9jrYxJA)在仔细看一下，然后再看这里的总结，相信会豁然开朗。

这里我尽量把逻辑的每一个细节都抠出来展现了，希望对大家有所帮助！


## 其他语言版本


Java：
  100. 相同的树:递归代码
  ```java
  class Solution {
    public boolean compare(TreeNode tree1, TreeNode tree2) {
       
        if(tree1==null && tree2==null)return true;
        if(tree1==null || tree2==null)return false;
        if(tree1.val!=tree2.val)return false;
        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        boolean compareLeft = compare(tree1.left, tree2.left);       // 左子树：左、 右子树：左
        boolean compareRight = compare(tree1.right, tree2.right);    // 左子树：右、 右子树：右
        boolean isSame = compareLeft && compareRight;                  // 左子树：中、 右子树：中（逻辑处理）
        return isSame;

    }
    boolean isSameTree(TreeNode p, TreeNode q) {
        return compare(p, q);
    }
}
  ```
  257. 二叉树的所有路径: 回溯代码
  ```java
  class Solution {
    public void traversal(TreeNode cur, List<Integer> path, List<String> result) {
        path.add(cur.val);
        // 这才到了叶子节点
        if (cur.left == null && cur.right == null) {
            String sPath="";
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += ""+path.get(i);
                sPath += "->";
            }
            sPath += path.get(path.size() - 1);
            result.add(sPath);
            return;
        }
        if (cur.left!=null) {
            traversal(cur.left, path, result);
            path.remove(path.size()-1); // 回溯
        }
        if (cur.right!=null) {
            traversal(cur.right, path, result);
            path.remove(path.size()-1); // 回溯
        }
    }
    
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new LinkedList<>();
        List<Integer> path = new LinkedList<>();
        if (root == null) return result;
        traversal(root, path, result);
        return result;
    }
}

  ```
  如下为精简之后的递归代码：(257. 二叉树的所有路径)
  ```java
  class Solution {
    public void traversal(TreeNode cur, String path, List<String> result) {
        path += cur.val; // 中
        if (cur.left == null && cur.right == null) {
            result.add(path);
            return;
        }
        if (cur.left!=null) traversal(cur.left, path + "->", result); // 左  回溯就隐藏在这里
        if (cur.right!=null) traversal(cur.right, path + "->", result); // 右 回溯就隐藏在这里
    }

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new LinkedList<>();
        String path = "";
        if (root == null) return result;
        traversal(root, path, result);
        return result;
    }
}
  ```

Python：


Go：




-----------------------
* 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
* B站视频：[代码随想录](https://space.bilibili.com/525438321)
* 知识星球：[代码随想录](https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ)
<div align="center"><img src=../pics/公众号.png width=450 alt=> </img></div>
