题目1
101. 对称二叉树【简单】
题解
以前做过，还是忘了…
如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称
递归
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root,root);
}
public boolean check(TreeNode l,TreeNode r){
if(l==null&&r==null)
return true;
if(l==null||r==null)
return false;
return l.val==r.val&&check(l.left,r.right)&&check(l.right,r.left);
}
}
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
迭代
用队列实现递归
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode>queue=new LinkedList<>();
queue.offer(root);
queue.offer(root);
while(!queue.isEmpty()){
TreeNode p=queue.poll();
TreeNode q=queue.poll();
if(p==null&&q==null)
continue;
if(p==null||q==null)
return false;
if(p.val!=q.val)
return false;
queue.offer(p.left);
queue.offer(q.right);
queue.offer(p.right);
queue.offer(q.left);
}
return true;
}
}
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
题目2
112. 路径总和【简单】
题解
BFS
利用树的层次遍历，增加一个队列存储 根节点到对应结点的路径长度，到叶子结点的时候判断是否等于targetSum（注意不能提前判断，因为树的结点可能有负值）
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null)
return false;
Queue<TreeNode>queueTree=new LinkedList<>();
Queue<Integer>queueVal=new LinkedList<>();
queueTree.offer(root);
queueVal.offer(root.val);
while(!queueTree.isEmpty()){
TreeNode p=queueTree.poll();
int sumTmp=queueVal.poll();
if(p.left==null&&p.right==null){
if(sumTmp==targetSum)
return true;
continue;
}
if(p.left!=null){
queueTree.offer(p.left);
queueVal.offer(p.left.val+sumTmp);
}
if(p.right!=null){
queueTree.offer(p.right);
queueVal.offer(p.right.val+sumTmp);
}
}
return false;
}
}
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
递归
从根节点到当前节点的值之和为 sum => 假定从根节点到当前节点的值之和为 val，是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。
相当于 自顶（根）向下 转换为了 自底（叶子）向上
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null)
return false;
int leftSum=targetSum-root.val;
if(root.left==null&&root.right==null)
return leftSum==0;
return hasPathSum(root.left,leftSum)||hasPathSum(root.right,leftSum);
}
}
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
p.s. 过了个清明节，没想到就五天没更了，今天急事儿有点多，刷题拖到了晚上，先过道简单题，明天开始继续努力！
|