<p align="center"> <a href="https://programmercarl.com/other/kstar.html" target="_blank"> <img src="https://code-thinking-1253855093.file.myqcloud.com/pics/20210924105952.png" width="1000"/> </a> <p align="center"><strong><a href="https://mp.weixin.qq.com/s/tqCxrMEU-ajQumL1i8im9A">参与本项目</a>,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!</strong></p> # 二叉树:以为使用了递归,其实还隐藏着回溯 > 补充一波 昨天的总结篇中[还在玩耍的你,该总结啦!(本周小结之二叉树)](https://programmercarl.com/周总结/20201003二叉树周末总结.html),有两处问题需要说明一波。 ## 求相同的树 [还在玩耍的你,该总结啦!(本周小结之二叉树)](https://programmercarl.com/周总结/20201003二叉树周末总结.html)中求100.相同的树的代码中,我笔误贴出了 求对称树的代码了,细心的同学应该都发现了。 那么如下我再给出求100. 相同的树 的代码,如下: ```CPP 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://programmercarl.com/0101.对称二叉树.html) 仅仅修改了变量的名字(为了符合判断相同树的语境)和 遍历的顺序。 大家应该会体会到:**认清[判断对称树](https://programmercarl.com/0101.对称二叉树.html)本质之后, 对称树的代码 稍作修改 就可以直接用来AC 100.相同的树。** ## 递归中隐藏着回溯 在[二叉树:找我的所有路径?](https://programmercarl.com/0257.二叉树的所有路径.html)中我强调了本题其实是用到了回溯的,并且给出了第一个版本的代码,把回溯的过程充分的提现了出来。 如下的代码充分的体现出回溯:(257. 二叉树的所有路径) ```CPP 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. 二叉树的所有路径) ```CPP 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依然是没有加上"->" 的,这就是回溯了。** 为了把这份精简代码的回溯过程展现出来,大家可以试一试把: ```CPP if (cur->left) traversal(cur->left, path + "->", result); // 左 回溯就隐藏在这里 ``` 改成如下代码: ```CPP path += "->"; traversal(cur->left, path, result); // 左 ``` 即: ``` CPP if (cur->left) { path += "->"; traversal(cur->left, path, result); // 左 } if (cur->right) { path += "->"; traversal(cur->right, path, result); // 右 } ``` 因为在递归右子树之前需要还原path,所以在左子树递归后必须为了右子树而进行回溯操作。而只右子树自己不添加回溯也可以成功AC。 因此,在上面代码的基础上,再加上左右子树的回溯代码,就可以AC了。 ```CPP 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依然是之前的数值(相当于回溯了)** 如果有点遗忘了,建议把这篇[二叉树:找我的所有路径?](https://programmercarl.com/0257.二叉树的所有路径.html)在仔细看一下,然后再看这里的总结,相信会豁然开朗。 这里我尽量把逻辑的每一个细节都抠出来展现了,希望对大家有所帮助! ## 其他语言版本 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: 100.相同的树 > 递归法 ```python 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.二叉的所有路径 > 递归中隐藏着回溯 ```python 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() #回溯 ``` > 精简版 ```python 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.相同的树 ```go /** * 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.二叉的所有路径 > 递归法 ```go /** * 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) } } ``` > 回溯法 ```go /** * 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.相同的树 ```javascript /** * 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.二叉树的不同路径 > 回溯法: ```javascript /** * 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; }; ``` Swift: > 100.相同的树 ```swift // 递归 func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool { return _isSameTree3(p, q) } func _isSameTree3(_ p: TreeNode?, _ q: TreeNode?) -> Bool { if p == nil && q == nil { return true } else if p == nil && q != nil { return false } else if p != nil && q == nil { return false } else if p!.val != q!.val { return false } let leftSide = _isSameTree3(p!.left, q!.left) let rightSide = _isSameTree3(p!.right, q!.right) return leftSide && rightSide } ``` > 257.二叉树的不同路径 ```swift // 递归/回溯 func binaryTreePaths(_ root: TreeNode?) -> [String] { var res = [String]() guard let root = root else { return res } var paths = [Int]() _binaryTreePaths3(root, res: &res, paths: &paths) return res } func _binaryTreePaths3(_ root: TreeNode, res: inout [String], paths: inout [Int]) { paths.append(root.val) if root.left == nil && root.right == nil { var str = "" for i in 0 ..< (paths.count - 1) { str.append("\(paths[i])->") } str.append("\(paths.last!)") res.append(str) } if let left = root.left { _binaryTreePaths3(left, res: &res, paths: &paths) paths.removeLast() } if let right = root.right { _binaryTreePaths3(right, res: &res, paths: &paths) paths.removeLast() } } ``` ----------------------- <div align="center"><img src=https://code-thinking.cdn.bcebos.com/pics/01二维码一.jpg width=500> </img></div>