100. 相同的树¹
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
1.递归*
public boolean isSameTree(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 isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
2.BFS
// 双队列,没必要
// Time:O(n), Space:O(n)
public boolean isSameTree(TreeNode p, TreeNode q) {
// 注意:这里的判断条件
if (p == null && q == null) return true;
if (p == null || q == null) return false;
Queue<TreeNode> queueP = new LinkedList<>();
Queue<TreeNode> queueQ = new LinkedList<>();
queueP.offer(p);
queueQ.offer(q);
while (!queueP.isEmpty() || !queueQ.isEmpty()) {
TreeNode p1 = queueP.poll();
TreeNode q1 = queueQ.poll();
// 1.两个都空
if (p1 == null && q1 == null) continue;
// 2.一个空
if (p1 == null || q1 == null) return false;
// 3.两个都不空
if (p1.val != q1.val ) return false;
// 注:这里的入队顺序:同一队中先左后右
queueP.offer(p1.left);
queueP.offer(p1.right);
queueQ.offer(q1.left);
queueQ.offer(q1.right);
}
return true;
}
// Time:O(n), Space:O(n)
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(p);
queue.offer(q);
while (!queue.isEmpty()) {
// 一次出两个节点就行了
TreeNode p1 = queue.poll();
TreeNode q1 = queue.poll();
if (p1 == null && q1 == null) continue;
if (p1 == null || q1 == null) return false;
if (p1.val != q1.val ) return false;
// 注:这里的入队顺序:先左后右
queue.offer(p1.left);
queue.offer(q1.left);
queue.offer(p1.right);
queue.offer(q1.right);
}
return true;
}
另外,Queue换成stack用迭代式的深度优先也可
98. 验证二叉搜索树²
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。
解法一:中序遍历
- 思路:二分搜索树中序遍历是,从小到大有序的
- 通过迭代形式,对二叉树遍历然后依次前后比较,当前每个节点的值都要大于之前遍历一个节点的值
- 注意:保存前一个值的变量,int会发生溢出,因此设为double且初始化为-MAX
- 复杂度
- Time:O(n)
- Space:O(n)
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
double inOrder = -Double.MAX_VALUE;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.val > inOrder) {
inOrder = root.val;
root = root.right;
}else
return false;
}
return true;
}
解法二:递归
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null)
return true;
// 每个节点如果超过这个范围,直接返回false
if (root.val >= maxVal || root.val <= minVal)
return false;
// 这里再分别以左右两个子节点分别判断,
// 左子树范围的最小值是minVal,最大值是当前节点的值,也就是root的值,因为左子树的值要比当前节点小
// 右子数范围的最大值是maxVal,最小值是当前节点的值,也就是root的值,因为右子树的值要比当前节点大
return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}
101. 对称的二叉树¹
请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
示例 1:
输入:root = [1,2,2,3,4,4,3]
输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3]
输出:false
限制:
0 <= 节点个数 <= 1000
注意:本题与主站 101 题相同:https://leetcode-cn.com/problems/symmetric-tree/
解法一:递归*
- 思路:明确对称特征,使用递归(只宏观去想,不要深入递归树)
- 根节点:为空时对称
- 第二级节点:必须相同
- 第 >= 三级节点:left.left = right.right && left.right = right.left
// Time:O(n), Space:O(n)
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode s, TreeNode t) {
if (s != null && t != null)
return s.val == t.val && isSymmetric(s.left, t.right) && isSymmetric(s.right, t.left);
else
return s == null && t == null;
}
}
解法二:迭代(栈)
迭代借助栈实现更好理解一点
// Time:O(n), Space:O(n)
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Stack<TreeNode> stack = new Stack<>();
stack.push(root.left);
stack.push(root.right);
while (!stack.isEmpty()) {
TreeNode r = stack.pop(), l = stack.pop();
// 1.两个节点都为空,则当前节点对称
if (r == null && l == null) continue;
// 2.一个节点为空,部队称
if (r == null || l == null) return false;
// 3.两个节点都非空,判断这两个节点是否相同
// 3.1 不同则不对称
if (r.val != l.val) return false;
// 3.2 相同,再按序入栈(这里的顺序必要一边left,一边right)
stack.push(r.left);
stack.push(l.right);
stack.push(r.right);
stack.push(l.left);
}
return true;
}
本文标题:【数据结构】二叉树:LeetCode题(四)100. 相同的树,98. 验证二叉搜索树,28. 对称的二叉树
本文链接:https://blog.quwenai.cn/post/10070.html
版权声明:本文不使用任何协议授权,您可以任何形式自由转载或使用。





还没有评论,来说两句吧...