这几道题其实很相似,所以可以放在一起理解。
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 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
使用深度优先遍历;
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
// 两棵树的当前节点都为null时,返回true
if(p == null && q == null) {
return true;
}
// 当其中一个是null,另外一个不是 null时,返回 false
if(p == null || q == null) {
return false
}
// 当两个都不为null,但是值不相等时,返回 false
if(p.val !== q.val) {
return false;
}
// 不断递归两颗树的左右子树
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [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
进阶:
你可以运用递归和迭代两种方法解决这个问题吗?
这个问题可以转化为 两个树在什么情况下互为镜像?
如果同时满足下面的条件,两个树互为镜像:
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
function isMirror(p, q) {
if(p == null && q == null) {
return true;
}
if(p == null || q == null) {
return false;
}
if(p.val !== q.val) {
return false;
}
return isMirror(p.left, q.right) && isMirror(p.right, q.left);
}
return isMirror(root, root);
};
翻转一棵二叉树。
示例:
输入:
4
/ \
2 7
/ \ / \
1 3 6 9
输出:
4
/ \
7 2
/ \ / \
9 6 3 1
递归的交换左右子树。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
// 当节点为 null 的时候直接返回
if(root === null) {
return root;
}
// 如果当前结点不为null,那么先将其左右子树进行翻转,然后交换左右子树
let right = invertTree(root.right);
let left = invertTree(root.left);
root.left = right;
root.right = left;
// 返回值为完成了翻转后的当前结点
return root;
};