NC16题解 | #对称的二叉树#

解法1：递归(成功)

import java.util.*;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null){
            return true;
        }
        return mirror(pRoot.left,pRoot.right);
    }
    public boolean mirror(TreeNode node1, TreeNode node2){
        if(node1 == null && node2 != null){
            return false;
        }
        if(node1 != null && node2 == null){
            return false;
        }
        if(node1 == null && node2 == null){
            return true;
        }
        if(node1.val != node2.val){
            return false;
        }else{
            return mirror(node1.left,node2.right) && mirror(node1.right, node2.left);
        }
        
    }
}

解法2：(半成品) 想用堆栈来输出成List来比较， 但是对于空节点这块还不太熟练，需要后续改进

public class Solution{
	boolean isSymmetrical(TreeNode pRoot) {
            List<Integer> list1 = dfsL(pRoot);
            List<Integer> list2 = dfsR(pRoot);
            for (int i = 0; i < list1.size(); i++) {
                if(!list1.get(i).equals(list2.get(i))){
                    return false;
                }
            }
            System.out.println();
            return true;
        }
        //栈1进行dfs(从左往右)
        public List<Integer> dfsL(TreeNode root){
            Stack<TreeNode> stack = new Stack();
            List<Integer> list = new ArrayList();
            if(root == null){
                return list;
            }
            TreeNode cur = root;
            while(!stack.isEmpty() || cur != null){
                while(cur!=null){
                    list.add(cur.val);
                    stack.push(cur);
                    cur=cur.left;
                }
                cur = stack.pop();
                cur = cur.right;
            }
            return list;
        }
        //栈2进行dfs(从右往左)
        public List<Integer> dfsR(TreeNode root){
            Stack<TreeNode> stack = new Stack();
            List<Integer> list = new ArrayList();
            if(root == null){
                return list;
            }
            TreeNode cur = root;
            while(cur != null || !stack.isEmpty()){
                while(cur!=null){
                    list.add(cur.val);
                    cur = cur.right;
                    stack.push(cur);
                }
                cur = stack.pop();
                cur = cur.left;
            }
            return list;
        }

}