算法通关村—轻松二叉树高频题目
二叉树里的双指针
判断两棵树是否相同
public boolean isSameTree(TreeNode p, TreeNode q) {
//如果都为空我们就认为他是相同的
if (p == null && q == null)
return true;
//如果一个为空,一个不为空,很明显不可能是相同的树,直接返回false即可
if (p == null || q == null)
return false;
//如果对应位置的两个结点的值不相等,自然也不是同一个棵树
if (p.val != q.val)
return false;
//走到这一步说明节点p和q是完全相同的,接下来需要再判断其左左和右右是否满足要求了
// 可以画图加深理解啊
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
对称二叉树
这个其实和上面的没什么区别,就是验证的是一棵树的左孩子和另一颗树的右孩子
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return false;
}
return varify(root.left, root.right);
}
public boolean varify(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
return varify(p.left, q.right) && varify(p.right, q.left);
}
}
合并二叉树
我自己画的图示,画的有点草率🤣
合并的节点有三种情况
- 两个节点都是 null
- 两个节点有一个是 null
- 两个节点都不是null
分情况考虑哦!
class Solution {
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;
}
}
路径专题
二叉树的所有路径
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
dfs(root, "", res);
return res;
}
/**
* 迭代实现计算路径
*/
public void dfs(TreeNode root, String path , List<String> res) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
res.add(path root.val);
return;
}
// 向向左到头遍历
dfs(root.left, path root.val "->", res);
// 在向右遍历
dfs(root.right, path root.val "->", res);
}
}
路径总和
class Solution {
/**
* 存储每一行的路径总和
*/
Map<Integer, Object> map = new HashMap<>();
/**
* @param root 根节点
* @param targetSum 路径总和
* @return 返回是否含有对应的 路径总和
*/
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
dfs(root, 0);
return map.containsKey(targetSum);
}
public void dfs(TreeNode root, int sum) {
if (root == null) {
return;
}
// 在这里加的原因是 可能有一些节点是只有一个孩子,但是还必须要加到路径之和里面去
sum = root.val;
// 如果到达根节点
if (root.right == null && root.left == null) {
// 这里要把计算出来的整到集合之中
map.put(sum, null);
return;
}
dfs(root.left, sum);
dfs(root.right, sum);
}
}
或者是这个写法
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
// 这里判断的意识是,如果这个传入的路径总和和减去处理叶节点的中和 和 叶节点的 val 相等的话,那么就是 ok 的
return targetSum == root.val;
}
boolean left = hasPathSum(root.left, targetSum - root.val) ;
boolean right = hasPathSum(root.right, targetSum - root.val);
// 只要有一路成功那么就是 ok 的
return left || right;
}
反转树
后序遍历
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
// 后序遍历
// 先反转后面的在反转前面的
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
前序遍历
class Solution {
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;
}
}
使用栈
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
// 将二叉树中的节点逐层放入队列中,再迭代处理队列中的元素
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
TreeNode temp = node.right;
node.right = node.left;
node.left = temp;
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return root;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgahiji
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13