树的子结构
题目描述
思路
遍历比对
遍历每个节点,看看它的子树的开头部分,也可能是一整棵,能不能完全匹配上目标
一些要注意的细节:
- B为空可直接返回false,这是题干,A为空也可直接返回false,这是题干隐含信息
- 比对过程中,递归到B为空则必定返回true,递归到A为空且B不为空则返回false
- 比对过程中,值不同,直接返回false
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(B==null||A==null) return false;
else return isEqual(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
}
public boolean isEqual(TreeNode A,TreeNode B){
if(B==null)return true;
if(A==null||A.val!=B.val) return false;
return isEqual(A.left,B.left)&&isEqual(A.right,B.right);
}
}
复杂度分析
M和N分别是A和B的节点数
时间复杂度
时间复杂度 O(MN)
遍历A树节点的函数遍历M次,每次比对最多N次
空间复杂度
空间复杂度 O(M)
遍历A树节点递归深度为M,比对时最大递归深度也为N
反思不足
思路
思路大题上与解答相似,但是实现细节上有很多不优雅之处
审题
空树不是任何树的子树,这句话的意思是空树也不是空树的子树
子结构不意味着子树
二叉树的镜像
题目描述
思路
迭代+递归
递归可以用来实现迭代
迭代节点是树的每个节点
迭代公式是交换值
迭代终止条件是原树已经遍历完全
迭代+辅助栈
可以用栈的形式逐渐推进深度,其实深度的推进本质是层序遍历
代码实现
迭代+递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root==null){
return null;
}
TreeNode newRoot = new TreeNode(root.val);
r(newRoot,root);
return newRoot;
}
public void r(TreeNode newRoot,TreeNode root){
if(root.right!=null){
newRoot.left=new TreeNode(root.right.val);
r(newRoot.left,root.right);
}
if(root.left!=null){
newRoot.right=new TreeNode(root.left.val);
r(newRoot.right,root.left);
}
return;
}
}
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
TreeNode tmp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(tmp);
return root;
}
}
迭代+辅助栈
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Stack<TreeNode> stack=new Stack<TreeNode>();
public TreeNode mirrorTree(TreeNode root) {
if(root==null){
return null;
}
stack.push(root);
while(!stack.empty()){
TreeNode cur = stack.pop();
if(cur.left!=null) stack.push(cur.left);
if(cur.right!=null) stack.push(cur.right);
TreeNode tmp =cur.left;
cur.left=cur.right;
cur.right=tmp;
}
return root;
}
}
复杂度分析
时间复杂度
均为O(N)
空间复杂度
递归做法为O(N),如果退化成链表就会达到
栈做法也为O(N),那种只有一边有的情况
反思不足
思路
我的思路是迭代,迭代公式为新创建树的左节点等于原树的右节点,右节点亦然
想到用递归实现,但是细节处理不好,不知道如何加深层次,不知道何时终止
没有看后面的提示,树可能为空
审题
没有看后面的提示,树可能为空
本题可以改变原树
对称的二叉树
题目描述
思路
求镜像+比对是否相同
即把第一题和第二题用到的思路结合起来
对称树的性质
- L=R
- L.L=R.R
- L.R=R.L
代码实现
求镜像+比对是否相同
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
TreeNode newRoot=new TreeNode(root.val);
r(newRoot,root);
return isEqual(newRoot,root);
}
public void r(TreeNode newRoot,TreeNode root){
if(root.left!=null){
newRoot.right=new TreeNode(root.left.val);
r(newRoot.right,root.left);
}
if(root.right!=null){
newRoot.left=new TreeNode(root.right.val);
r(newRoot.left,root.right);
}
return;
}
public boolean isEqual(TreeNode a,TreeNode b){
if(b==null&&a==null)return true;
if((b==null&&a!=null)||(b!=null&&a==null)||(a.val!=b.val))return false;
return isEqual(a.left,b.left)&&isEqual(a.right,b.right);
}
}
对称树的性质
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return valueIsEqual(root.left,root.right);
}
//1是左节点，2是右节点
public boolean valueIsEqual(TreeNode node1,TreeNode node2){
if(node1==null&&node2==null)return true;
if(node1==null||node2==null||node1.val!=node2.val)return false;
return valueIsEqual(node1.left,node2.right)&&valueIsEqual(node1.right,node2.left);
}
}
复杂度分析
时间复杂度
均为O(N)
空间复杂度
均为O(N)
但实际上方法1要差一点,有一颗新树
后者极端情况为N/2,两边一条线那种
反思不足
思路
标签：right,TreeNode,offer,day07,return,null,root,left From： https://www.cnblogs.com/zhouj-learn/p/16786097.html自己的思路也就是方法一没什么问题,就是代码量有点大
不知道这种性质,也没想过要去思考挖掘性质和规律