26 树的子结构
- 题目描述
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构) - 解析
如果B为A的子树,则B是以A根节点构成的子树,或者是A的左节点,或者是A的右节点的子树,即可以递归来完成
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null) return false;
//要么b为a的子树,要么b为a左孩子的子树,要么b为a右孩子的子树
return judge(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
public boolean judge(TreeNode A, TreeNode B){
if(B == null) return true;
if(A == null) return false;
if(A.val != B.val) return false;
return judge(A.left, B.left) && judge(A.right, B.right);
}
27 二叉树镜像
- 题目描述:
请完成一个函数,输入一个二叉树,该函数输出它的镜像。与226 翻转二叉树相同。 - 解析
使用递归的方法:每次都构建一个节点的左孩子右孩子
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
TreeNode node = new TreeNode(root.val);
node.left = mirrorTree(root.right);
node.right = mirrorTree(root.left);
return node;
}
使用双向队列:层序遍历整棵树,将树的左右节点交换顺序
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
Deque<TreeNode> queue = new LinkedList<>();
queue.addLast(root);
while(!queue.isEmpty()){
int size = queue.size();
TreeNode node = queue.removeFirst();
if(node.left != null) queue.addLast(node.left);
if(node.right != null) queue.addLast(node.right);
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
return root;
}
28 对称的二叉树
- 题目描述
请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。 - 解析
使用一个队列来保存节点:每次都选择在镜像中需要对比的两个节点–迭代
public boolean isSymmetric(TreeNode root) {
if(root == null || root.left == null && root.right == null) return true;
Deque<TreeNode> queue = new LinkedList<>();
//将根节点压入栈两次
queue.offer(root);
queue.offer(root);
while(!queue.isEmpty()){
TreeNode one = queue.poll();
TreeNode two = queue.poll();
if(one == null && two == null) continue;
if((one == null || two == null) || one.val != two.val) return false;
queue.offer(one.left);
queue.offer(two.right);
queue.offer(one.right);
queue.offer(two.left);
}
return true;
}
使用递归法:
public boolean isSymmetric(TreeNode root) {
//递归法:每次判断左节点的左孩子和右节点的右孩子,左节点的右孩子和右节点的左孩子
if(root == null) return true;
return judge(root.left, root.right);
}
public boolean judge(TreeNode node1, TreeNode node2){
if(node1 == null && node2 == null) return true;
if(node1 == null || node2 == null) return false;
if(node1.val != node2.val) return false;
return judge(node1.left, node2.right) && judge(node1.right, node2.left);
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)