題目

101.?對稱二叉樹?

思路

使用層序遍歷，遍歷當前層的節(jié)點時，如該節(jié)點的左（右）孩子為空，在list中添加null，否則加入左（右）孩子的值。每遍歷完一層則對當前l(fā)ist進行判斷，這里判斷我用了一個很笨的方法，前面記錄下一層節(jié)點值時就設置了兩個list，其中一個用來翻轉，然后判斷這兩個list是否相等來判斷數(shù)是否為對稱樹。

去看了解析，有兩種方法：遞歸法、使用雙端隊列進行迭代。

代碼

public boolean isSymmetric(TreeNode root) {
//        迭代寫法：使用雙端隊列if(root == null){return true;}Deque<TreeNode> deque = new LinkedList<TreeNode>();deque.offerFirst(root.left);deque.offerLast(root.right);while (!deque.isEmpty()){TreeNode temp_left = deque.pollFirst();TreeNode temp_right = deque.pollLast();if(temp_left == null && temp_right == null){continue;}if(temp_left == null || temp_right == null || temp_left.val != temp_right.val){return false;}deque.offerFirst(temp_left.right);deque.offerFirst(temp_left.left);deque.offerLast(temp_right.left);deque.offerLast(temp_right.right);}return true;}public boolean isSymmetric_2(TreeNode root) {
//        遞歸寫法：分解為判斷每個子樹是否對稱if(root == null){return true;}return comp(root.left, root.right);}public boolean comp(TreeNode left, TreeNode right){if(left == null && right != null){return false;}if(left != null && right == null) {return false;}if(left == null && right == null){return true;}if(left.val != right.val){return false;}
//        當左右子樹都不為空且值相等時，對其左右子樹繼續(xù)進行判斷return comp(left.left, right.right)&&comp(left.right, right.left);}public boolean isSymmetric_1(TreeNode root) {
//        判斷二叉樹是否為軸對稱二叉樹
//        直接拿層序遍歷的結果，看逆轉后是否還為原數(shù)組來進行判斷if(root == null){return false;}Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.add(root);while (!queue.isEmpty()){int len = queue.size();List<Integer> temp_list = new ArrayList<Integer>();List<Integer> temp_re = new ArrayList<Integer>();while (len > 0){TreeNode temp = queue.poll();if(temp.left == null){temp_list.add(null);temp_re.add(null);}if(temp.left != null){queue.add(temp.left);temp_list.add(temp.left.val);temp_re.add(temp.left.val);}if(temp.right == null){temp_list.add(null);temp_re.add(null);}if(temp.right != null){queue.add(temp.right);temp_list.add(temp.right.val);temp_re.add(temp.right.val);}len--;}Collections.reverse(temp_list);if(!temp_list.equals(temp_re)){return false;}}return true;}