编程导航算法村第八关 | 树的深度优先遍历
判断两棵树是否相同
- LeetCode100:给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
- 思路:
- 两课树同时进行前序遍历,比较节点是否相等
public boolean isSameTree(TreeNode p, TreeNode q) {
return preNode(p, q);
}
public boolean preNode(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p!=null && q!=null && p.val != q.val) {
return false;
}
return preNode(p.left, q.left) && preNode(p.right, q.right);
}
对称二叉树
- LeetCode101 给定一个二叉树,检查它是否是镜像对称的。
- 思路:
- 两颗树同时进行前序遍,root.left安装前左右的顺序遍历、 root.right按照前右左的顺序遍历,比较节点是否相等
// 对称二叉树
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Boolean b = preNode(root.left, root.right);
return b;
}
Boolean preNode(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return preNode(left.left, right.right) && preNode(left.right, right.left);
}
合并二叉树
- LeetCode617.给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
- 思路:
- 对一个节点进行合并之后,还要对该节点的左右子树分别进行合并
- 如果两个节点非空,新节点就是两个节点的和
- 如果一个节点为空,则是另一个非空节点
// 合并到root1上
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
TreeNode merge = new TreeNode(root1.val + root2.val);
merge.left = mergeTrees(root1.left, root2.left);
merge.right = mergeTrees(root1.right, root2.right);
return merge;
}
二叉树的所有路径
LeetCode257:给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点是指没有子节点的节点。文章来源:https://www.toymoban.com/news/detail-625782.html
- 思路:
- 采用深度优先遍历
- 找到叶子结点后,添加路径到结果集中
public List<String> binaryTreePaths(TreeNode root) {
final ArrayList<String> result = new ArrayList<>();
dfs(root, "", result);
return result;
}
void dfs(TreeNode root, String path, List<String> res) {
if (root==null){
return;
}
path += root.val;
if (root.left != null || root.right != null) {
path += "->";
}
if (root!=null && root.left == null && root.right==null) {
res.add(path);
}
dfs(root.left, path, res);
dfs(root.right, path, res);
}
路径总和
上面我们讨论的找所有路径的方法,那我们是否可以再找一下哪条路径的和为目标值呢?这就是LeetCode112题:给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ,判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum。叶子节点 是指没有子节点的节点。文章来源地址https://www.toymoban.com/news/detail-625782.html
- 思路:
- 使用dfs算法,找出所有路径的节点和,然后判断目标值是否在节点和列表中
public boolean hasPathSum(TreeNode root, int targetSum) {
final ArrayList<Integer> result = new ArrayList<>();
dfs(root, 0, result);
if (result.contains(targetSum)) {
return true;
}
return false;
}
void dfs(TreeNode root, int currentSum, List<Integer> result) {
if (root == null) {
return;
}
currentSum += root.val;
if (root.left == null && root.right == null) {
result.add(currentSum);
}
dfs(root.left, currentSum, result);
dfs(root.right, currentSum, result);
}
- 方法二:
- 判断targetSum是否存在的问题可以转化为,判断叶子结点的值是否等于targetSum-这条路径上所有节点的和的问题
- 左右子树分别判断
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
boolean left = hasPathSum(root.left, targetSum - root.val);
boolean right = hasPathSum(root.right, targetSum - root.val);
return left || right;
}
二叉树的反转
- LeetCode226 翻转二叉树,将二叉树整体反转
- 思路:
- 深度优先算法:翻转左右子树
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
到了这里,关于编程导航算法村第八关 | 树的深度优先遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!