給定一個二叉樹筐付，檢查它是否是鏡像對稱的啊片。
例如涛浙，二叉樹 [1,2,2,3,4,4,3] 是對稱的。
image.png
但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:
image.png
法一：遞歸調用
class Solution {
public boolean isSymmetric(TreeNode root) {
//遞歸
if(root==null)
return true;
//空節(jié)點是特殊二叉樹
return dfs(root.left,root.right);
}
public boolean dfs(TreeNode p,TreeNode q){
//當有一個為空然磷，另一個必須也為空
if(p==null || q==null)
return (p==null)&&(q==null);
//左邊往左走右邊就得往右走以求對稱
//一旦有一點不對稱立即返回false
return p.val==q.val && dfs(p.left,q.right) && dfs(p.right,q.left);
}
}
法二：迭代法
（利用94題的中序遍歷【LDR】的步驟郑趁，左邊一樣，右邊反著來）
（94題是開一個棧姿搜，將tree.left的結點（1寡润、2捆憎、4、8）壓入棧梭纹，等right遍歷完就pop）
先放一個94題的代碼
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
//先畫出一棵深度為4的樹以幫助理解記憶
//建立一個棧躲惰，將tree.left（1、2变抽、4础拨、8···）壓入棧，每次取出
//將排序好的放入鏈表中绍载，最后返回鏈表
List <Integer> res = new ArrayList<>();
Stack <TreeNode>stack=new Stack<>();
TreeNode p=root;
while(p!=null || !stack.isEmpty()){
while(p!=null){
stack.push(p);
p=p.left;
}
p=stack.pop();
res.add(p.val);
p=p.right;
}
return res;
}
}
接下來回歸正題101
這次要建立兩個棧分別用來存左邊和右邊的節(jié)點
class Solution {
public boolean isSymmetric(TreeNode root) {
//遞歸
if(root==null)
return true;
Stack <TreeNode> stkleft=new Stack<>();
Stack <TreeNode> stkright=new Stack<>();
TreeNode l=root.left, r=root.right;
while(l!=null || r!=null || !stkleft.empty() || !stkright.empty()){
while( (l!=null) && (r!=null) ){
stkleft.push(l);
stkright.push(r);
l=l.left;
r=r.right;
}
//結束循環(huán)之后一個空一個不空就返回false
if(l!=null || r!=null)
return false;
//成功的話要給l和r賦值诡宗，并把使用過的點pop出來
l=stkleft.pop();
r=stkright.pop();
if(l.val!=r.val)
return false;
//否則的話，把l的左子樹加進來逛钻，r的右子樹加進來
l=l.right;
r=r.left;
}
return true;
}
}
迭代還可以用隊列的方法······
