100. Same Tree

Link

難易度 : Easy

題目給予兩個binary tree並且要求判斷兩棵樹是否相同

解題思路其實與101. Symmetric Tree非常類似，關鍵在於配對比較的節點不太一樣稍微修改就可以，因此作法只要參考上面那篇即可

這邊我一樣實作了三種解法
第一種是最基礎的recursive的作法

recursive

    //recursive
    class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            return Compare(p,q);
        }

        private boolean Compare(TreeNode left,TreeNode right) 
        {
            if(left==null&&right==null) 
            {
                return true;
            }
            else if(left==null&&right!=null) 
            {
                return false;
            }
            else if(left!=null&&right==null) 
            {
                return false;
            }
            else if(left.val!=right.val) 
            {
                return false;
            }

            return Compare(left.left,right.left)&&Compare(left.right,right.right);
        }
    }

接下來是使用deque來實作的iteratively做法

iteratively by deque

    //iteratively
    class Solution2 {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            Deque<TreeNode> deque = new LinkedList<TreeNode>();
            deque.push(p);
            deque.push(q);
            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.left);
                deque.offerFirst(left.right);
                deque.offerLast(right.left);
                deque.offerLast(right.right);
            }
            return true;
        }   
    }

最後是使用queue來實現的iteratively的作法

iteratively by queue

    //iteratively
    class Solution3 {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            Queue<TreeNode> que = new LinkedList<TreeNode>();
            que.add(p);
            que.add(q);
            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.left);
                que.add(left.right);
                que.add(right.right);
            }
            return true;
        }   
    }