对称树:
//===================Mirror递归算法(理解递归)=============================//
通过求其镜像二叉树,然后判断这两树是否相同。几个子函数都用了递归。
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
void Mirror(TreeNode root){//求树的镜像树
if(root==null) return;
Mirror(root.left);
Mirror(root.right);
if(root.left!=null||root.right!=null)
{
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
}
boolean isSameTree(TreeNode t1,TreeNode t2){//判断两棵树是否相同
if(t1==null&&t2==null) return true;
else if(t1!=null&&t2!=null&&t1.val==t2.val){
boolean left=isSameTree(t1.left,t2.left);
boolean right=isSameTree(t1.right,t2.right);
return left&&right;
}else
return false;
}
TreeNode copyTree(TreeNode root){//复制一棵树
if(root==null) return null;
TreeNode t=new TreeNode(root.val);
t.left=copyTree(root.left);
t.right=copyTree(root.right);
return t;
}
boolean isSymmetrical(TreeNode pRoot)
{
TreeNode temp=copyTree(pRoot);
Mirror(pRoot);
return isSameTree(temp,pRoot);
}
}
//===================isMirror递归算法2=============================//
1.只要pRoot.left和pRoot.right对称即可
2.左右节点的值相等且对称子树left.left, right.right ;left.rigth,right.left也对称
/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public boolean jude(TreeNode node1,TreeNode node2){ if(node1==null&&node2==null){ return true; }else if(node1==null||node2==null) return false; if(node1.val!=node2.val) return false; else{ return jude(node1.left,node2.right)&&jude(node1.right,node2.left); } } public boolean isSymmetrical(TreeNode pRoot) { return pRoot==null||jude(pRoot.left,pRoot.right); } }
//===================非递归算法,利用DFS和BFS=============================//
DFS:成对出栈入栈
/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ import java.util.*; //队列的进队出队:Q.offer(object) Q.poll() public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot == null) return true;//1.树null时直接返回true //2.树不空 Stack<TreeNode> s = new Stack<>(); s.push(pRoot.left); s.push(pRoot.right); while(!s.empty()) { TreeNode right = s.pop();//成对取出 TreeNode left = s.pop(); //首先是要结构对称 if(left == null && right == null) continue; else if(left == null || right == null) return false; //然后要保证对称位置上的数据相等 if(left.val != right.val) return false; else{ s.push(left.left);//成对插入 left.left对应right.right ;left.rigth对应right.left s.push(right.right); s.push(left.right); s.push(right.left); } } return true; } }
BFS:
import java.util.*; //队列的进队出队:Q.offer(object) Q.poll() public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot==null) return true; Queue<TreeNode> Q=new LinkedList<>(); Q.offer(pRoot.left);//成对入队 Q.offer(pRoot.right); while(!Q.isEmpty()){ TreeNode left=Q.poll();//成对出队 TreeNode right=Q.poll(); //首先是要结构对称 if(left==null&&right==null) continue; else if(left==null||right==null) return false; //然后要保证对称位置上的数据相等 if(left.val!=right.val) return false; else{ Q.offer(left.left); Q.offer(right.right); Q.offer(left.right); Q.offer(right.left); } } return true; } }