参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!
补充一波
昨天的总结篇中还在玩耍的你,该总结啦!(本周小结之二叉树),有两处问题需要说明一波。
还在玩耍的你,该总结啦!(本周小结之二叉树)中求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依然是之前的数值(相当于回溯了)
如果有点遗忘了,建议把这篇二叉树:找我的所有路径?在仔细看一下,然后再看这里的总结,相信会豁然开朗。
这里我尽量把逻辑的每一个细节都抠出来展现了,希望对大家有所帮助!
- 相同的树:递归代码
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;
}
}
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) #右 回溯就隐藏在这里
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]//回溯
}
}
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;
};
相同的树
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (p === null && q === null) return true;
if (p === null || q === null) return false;
if (p.val !== q.val) return false;
let bool1: boolean, bool2: boolean;
bool1 = isSameTree(p.left, q.left);
bool2 = isSameTree(p.right, q.right);
return bool1 && bool2;
};
二叉树的不同路径
function binaryTreePaths(root: TreeNode | null): string[] {
function recur(node: TreeNode, nodeSeqArr: number[], resArr: string[]): void {
nodeSeqArr.push(node.val);
if (node.left === null && node.right === null) {
resArr.push(nodeSeqArr.join('->'));
}
if (node.left !== null) {
recur(node.left, nodeSeqArr, resArr);
nodeSeqArr.pop();
}
if (node.right !== null) {
recur(node.right, nodeSeqArr, resArr);
nodeSeqArr.pop();
}
}
let nodeSeqArr: number[] = [];
let resArr: string[] = [];
if (root === null) return resArr;
recur(root, nodeSeqArr, resArr);
return resArr;
};
100.相同的树
// 递归
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.二叉树的不同路径
// 递归/回溯
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()
}
}
100.相同的树
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn is_same_tree(
p: Option<Rc<RefCell<TreeNode>>>,
q: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
match (p, q) {
(None, None) => true,
(None, Some(_)) => false,
(Some(_), None) => false,
(Some(n1), Some(n2)) => {
if n1.borrow().val == n2.borrow().val {
let right =
Self::is_same_tree(n1.borrow().left.clone(), n2.borrow().left.clone());
let left =
Self::is_same_tree(n1.borrow().right.clone(), n2.borrow().right.clone());
right && left
} else {
false
}
}
}
}
}
257.二叉树的不同路径
// 递归
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn binary_tree_paths(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<String> {
let mut res = vec![];
let mut path = vec![];
Self::recur(&root, &mut path, &mut res);
res
}
pub fn recur(
root: &Option<Rc<RefCell<TreeNode>>>,
path: &mut Vec<String>,
res: &mut Vec<String>,
) {
let node = root.as_ref().unwrap().borrow();
path.push(node.val.to_string());
if node.left.is_none() && node.right.is_none() {
res.push(path.join("->"));
return;
}
if node.left.is_some() {
Self::recur(&node.left, path, res);
path.pop(); //回溯
}
if node.right.is_some() {
Self::recur(&node.right, path, res);
path.pop(); //回溯
}
}
}