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

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

补充一波

昨天的总结篇中还在玩耍的你,该总结啦!(本周小结之二叉树) (opens new window),有两处问题需要说明一波。

# 求相同的树

还在玩耍的你,该总结啦!(本周小结之二叉树) (opens new window)中求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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

以上的代码相对于:二叉树:我对称么? (opens new window) 仅仅修改了变量的名字(为了符合判断相同树的语境)和 遍历的顺序。

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

# 递归中隐藏着回溯

二叉树:找我的所有路径? (opens new window)中我强调了本题其实是用到了回溯的,并且给出了第一个版本的代码,把回溯的过程充分的提现了出来。

如下的代码充分的体现出回溯:(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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

如下为精简之后的递归代码:(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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

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

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

改成如下代码:

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

即:


if (cur->left) {
    path += "->";
    traversal(cur->left, path, result); // 左
}
if (cur->right) {
    path += "->";
    traversal(cur->right, path, result); // 右
}
1
2
3
4
5
6
7
8
9

因为在递归右子树之前需要还原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(); 
}
1
2
3
4
5
6
7
8
9
10
11
12

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

如果有点遗忘了,建议把这篇二叉树:找我的所有路径? (opens new window)在仔细看一下,然后再看这里的总结,相信会豁然开朗。

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

# 其他语言版本

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);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  1. 二叉树的所有路径: 回溯代码
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;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

如下为精简之后的递归代码:(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;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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() #回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

精简版

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) #右 回溯就隐藏在这里
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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)
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

回溯法

/**
 * 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]//回溯
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42