参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

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

补充一波

昨天的总结篇中还在玩耍的你，该总结啦！（本周小结之二叉树），有两处问题需要说明一波。

求相同的树

还在玩耍的你，该总结啦！（本周小结之二叉树）中求100.相同的树的代码中，我笔误贴出了求对称树的代码了，细心的同学应该都发现了。

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

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);
    }
};

以上的代码相对于：二叉树：我对称么？仅仅修改了变量的名字（为了符合判断相同树的语境）和遍历的顺序。

大家应该会体会到：认清判断对称树本质之后，对称树的代码稍作修改就可以直接用来AC 100.相同的树。

递归中隐藏着回溯

在二叉树：找我的所有路径？中我强调了本题其实是用到了回溯的，并且给出了第一个版本的代码，把回溯的过程充分的提现了出来。

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

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); // 右
}

因为在递归右子树之前需要还原path，所以在左子树递归后必须为了右子树而进行回溯操作。而只右子树自己不添加回溯也可以成功AC。

因此，在上面代码的基础上，再加上左右子树的回溯代码，就可以AC了。

if (cur->left) {
    path += "->";
    traversal(cur->left, path, result); // 左
    path.pop_back(); // 回溯，抛掉val
    path.pop_back(); // 回溯，抛掉->
}
if (cur->right) {
    path += "->";
    traversal(cur->right, path, result); // 右
    path.pop_back(); // 回溯（非必要）
    path.pop_back(); 
}

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

如果有点遗忘了，建议把这篇二叉树：找我的所有路径？在仔细看一下，然后再看这里的总结，相信会豁然开朗。

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

其他语言版本

Java： 100. 相同的树:递归代码

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);
  }
}

二叉树的所有路径: 回溯代码

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. 二叉树的所有路径)

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：

100.相同的树

递归法

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        return self.compare(p, q)
        
    def compare(self, tree1, tree2):
        if not tree1 and tree2:
            return False
        elif tree1 and not tree2:
            return False
        elif not tree1 and not tree2:
            return True
        elif tree1.val != tree2.val: #注意这里我没有使用else
            return False
        
        #此时就是：左右节点都不为空，且数值相同的情况
        #此时才做递归，做下一层的判断
        compareLeft = self.compare(tree1.left, tree2.left) #左子树：左、 右子树：左
        compareRight = self.compare(tree1.right, tree2.right) #左子树：右、 右子树：右
        isSame = compareLeft and compareRight #左子树：中、 右子树：中（逻辑处理）
        return isSame

257.二叉的所有路径

递归中隐藏着回溯

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        result = []
        path = []
        if not root:
            return result
        self.traversal(root, path, result)
        return result
        
    def traversal(self, cur, path, result):
        path.append(cur.val)
        #这才到了叶子节点
        if not cur.left and not cur.right:
            sPath = ""
            for i in range(len(path)-1):
                sPath += str(path[i])
                sPath += "->"
            sPath += str(path[len(path)-1])
            result.append(sPath)
            return
        if cur.left:
            self.traversal(cur.left, path, result)
            path.pop() #回溯
        if cur.right:
            self.traversal(cur.right, path, result)
            path.pop() #回溯

精简版

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        result = []
        path = ""
        if not root:
            return result
        self.traversal(root, path, result)
        return result
        
    def traversal(self, cur, path, result):
        path += str(cur.val) #中
        if not cur.left and not cur.right:
            result.append(path)
            return
        if cur.left:
            self.traversal(cur.left, path+"->", result) #左  回溯就隐藏在这里
        if cur.right:
            self.traversal(cur.right, path+"->", result) #右 回溯就隐藏在这里

Go：

100.相同的树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
   	switch {
	case p == nil && q == nil:
		return true
	case p == nil || q == nil:
		fallthrough
	case p.Val != q.Val:
		return false
	}
	return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

257.二叉的所有路径

递归法

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func binaryTreePaths(root *TreeNode) []string {
    var result []string
    traversal(root,&result,"")
    return result
}
func traversal(root *TreeNode,result *[]string,pathStr string){
    //判断是否为第一个元素
    if len(pathStr)!=0{
        pathStr=pathStr+"->"+strconv.Itoa(root.Val)
    }else{
        pathStr=strconv.Itoa(root.Val)
    }
    //判断是否为叶子节点
    if root.Left==nil&&root.Right==nil{
        *result=append(*result,pathStr)
        return 
    }
    //左右
    if root.Left!=nil{
        traversal(root.Left,result,pathStr)
    }
    if root.Right!=nil{
        traversal(root.Right,result,pathStr)
    }
}

回溯法

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func binaryTreePaths(root *TreeNode) []string {
    var result []string
    var path   []int
    traversal(root,&result,&path)
    return result
}
func traversal(root *TreeNode,result *[]string,path *[]int){
    *path=append(*path,root.Val)
    //判断是否为叶子节点
    if root.Left==nil&&root.Right==nil{
        pathStr:=strconv.Itoa((*path)[0])
        for i:=1;i<len(*path);i++{
            pathStr=pathStr+"->"+strconv.Itoa((*path)[i])
        }
        *result=append(*result,pathStr)
        return 
    }
    //左右
    if root.Left!=nil{
        traversal(root.Left,result,path)
        *path=(*path)[:len(*path)-1]//回溯到上一个节点（因为traversal会加下一个节点值到path中）
    }
    if root.Right!=nil{
        traversal(root.Right,result,path)
        *path=(*path)[:len(*path)-1]//回溯
    }
}

JavaScript：

100.相同的树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (p === null && q === null) {
        return true;
    } else if (p === null || q === null) {
        return false;
    } else if (p.val !== q.val) {
        return false;
    } else {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
};

257.二叉树的不同路径

回溯法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    const getPath = (root, path, result) => {
        path.push(root.val);
        if (root.left === null && root.right === null) {
            let n = path.length;
            let str = '';
            for (let i=0; i<n-1; i++) {
                str += path[i] + '->';
            }
            str += path[n-1];
            result.push(str);
        }

        if (root.left !== null) {
            getPath(root.left, path, result);
            path.pop();   // 回溯
        }

        if (root.right !== null) {
            getPath(root.right, path, result);
            path.pop(); 
        }
    }
    
    if (root === null) return [];
    let result = [];
    let path = [];
    getPath(root, path, result);
    return result;
};

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

二叉树中递归带着回溯.md

二叉树中递归带着回溯.md

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

求相同的树

递归中隐藏着回溯

其他语言版本

Files

二叉树中递归带着回溯.md

Latest commit

History

二叉树中递归带着回溯.md

File metadata and controls

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

求相同的树

递归中隐藏着回溯

其他语言版本