101. Symmetric Tree

Link

難易度 : Easy

這次題目給了一個root，要求判斷這個tree是不是完全對稱的，也就是不只node的位置對稱、node.val也是對稱

解題思路分成兩個步驟

1. 同層對稱位置上的節點比較
2. 配對對稱位置的節點

如圖所示，第二層的兩個node處在互相對稱的位置上
那要有哪些條件會導致節點不對稱呢?

1. 兩個節點一方為null且另一方不為null
2. 兩個節點皆不為null但val不相等

因此節點對稱的條件也列出來了

1. 兩節點皆為null
2. 兩節點皆不為null且val相等

只要符合節點對稱，我們就可以繼續尋找下一配對的節點來比較，也就是思路的第二點

其實可以看得出來配對的邏輯就是

上層節點的外側配外側(紅線)，內側配內側(藍線)

有了上述的思路後就可以簡單的先寫出recursive的作法

recursive

    //recursive
    class Solution
    {
        public boolean isSymmetric(TreeNode root)
        {
            return Compare(root.left,root.right);
        }

        private boolean Compare(TreeNode left,TreeNode right) 
        {
            //節點有任一方為null的情況
            if(left==null&&right==null) 
            {
                return true;
            }
            else if(left==null&&right!=null) 
            {
                return false;
            }
            else if(left!=null&&right==null) 
            {
                return false;
            }
            //兩節點不為null但是val不相等
            else if(left.val!=right.val) 
            {
                return false;
            }

            //兩節點不為null且val相等
            //向下層開始判斷
            return Compare(left.left,right.right)&&Compare(left.right,right.left);
        }
    }

那麼要怎麼將過程用iteratively表現出來呢?
這邊我用了兩種做法
一開始想到的是使用deque來實現雙頭進出，這樣在塞node進去時比較靈活一點

iteratively by deque

    //iteratively 
    class Solution2
    {
        public boolean isSymmetric(TreeNode root)
        {
            Deque<TreeNode> deque = new LinkedList<TreeNode>();
            deque.push(root.left);
            deque.push(root.right);
            while(!deque.isEmpty()) 
            {
                TreeNode left = deque.pollFirst();
                TreeNode right = deque.pollLast();

                if(left==null&&right==null) 
                {
                    continue;
                }
                else if(left==null&&right!=null) 
                {
                    return false;
                }
                else if(left!=null&&right==null) 
                {
                    return false;
                }
                else if(left.val!=right.val) 
                {
                    return false;
                }

                deque.offerFirst(left.right);
                deque.offerFirst(left.left);
                deque.offerLast(right.left);
                deque.offerLast(right.right);
            }
            return true;
        }
    }

另一種是用queue來實現，因為queue出口單一，所以在塞node進去時要注意順序

iteratively by queue

    //iteratively 
    class Solution3
    {
        public boolean isSymmetric(TreeNode root)
        {
            Queue<TreeNode> que = new LinkedList<TreeNode>();
            que.add(root.left);
            que.add(root.right);
            while(!que.isEmpty()) 
            {
                TreeNode left = que.poll();
                TreeNode right = que.poll();
                if(left==null&&right==null) 
                {
                    continue;
                }
                else if(left==null&&right!=null) 
                {
                    return false;
                }
                else if(left!=null&&right==null) 
                {
                    return false;
                }
                else if(left.val!=right.val) 
                {
                    return false;
                }

                que.add(left.left);
                que.add(right.right);
                que.add(left.right);
                que.add(right.left);
            }
            return true;

        }
    }