572. Subtree of Another Tree

Link

難易度 : Easy

題目給予一個root一個subRoot並且要求判斷subRoot下的tree是否為root下的subTree。

這題的關鍵思路與100. Same Tree是一模一樣的，因此我們只需要用上一題的作法做擴充即可完成

擴充的部分其實就是很單純的遍尋binary tree的作法，直到所有node遍尋過都不符合subTree就代表結果為false

一樣提供三種解法

recursive

    // recursive
    class Solution
    {
        public boolean isSubtree(TreeNode root, TreeNode subRoot)
        {
            Queue<TreeNode> que = new LinkedList<TreeNode>();
            que.add(root);
            while (!que.isEmpty())
            {
                TreeNode current = que.poll();
                if (Compare(current, subRoot))
                {
                    return true;
                }
                if (current != null)
                {
                    que.add(current.left);
                    que.add(current.right);
                }
            }
            return false;
        }

        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);
        }
    }

再來是兩種類似的iteratively的解法

iteratively by deque

    // iteratively
    class Solution2
    {
        public boolean isSubtree(TreeNode root, TreeNode subRoot)
        {
            Queue<TreeNode> mainQ = new LinkedList<TreeNode>();
            mainQ.add(root);
            while (!mainQ.isEmpty())
            {
                TreeNode current = mainQ.poll();
                boolean isBreak = false;
                Deque<TreeNode> deque = new LinkedList<TreeNode>();
                if(current==null) 
                {
                    continue;
                }
                deque.offerFirst(current);
                deque.offerLast(subRoot);
                while (!deque.isEmpty())
                {
                    TreeNode left = deque.pollFirst();
                    TreeNode right = deque.pollLast();

                    if (left == null && right == null)
                    {
                        continue;
                    }
                    else if (left == null && right != null)
                    {
                        isBreak = true;
                        break;
                    }
                    else if (left != null && right == null)
                    {
                        isBreak = true;
                        break;
                    }
                    else if (left.val != right.val)
                    {
                        isBreak = true;
                        break;
                    }

                    deque.offerFirst(left.left);
                    deque.offerFirst(left.right);
                    deque.offerLast(right.left);
                    deque.offerLast(right.right);
                }
                if (!isBreak)
                {
                    return true;
                }
                mainQ.add(current.left);
                mainQ.add(current.right);
            }
            return false;
        }
    }

iteratively by queue

    // iteratively
    class Solution3
    {
        public boolean isSubtree(TreeNode root, TreeNode subRoot)
        {
            Queue<TreeNode> mainQ = new LinkedList<TreeNode>();
            mainQ.add(root);
            while (!mainQ.isEmpty())
            {
                Queue<TreeNode> que = new LinkedList<TreeNode>();
                TreeNode current = mainQ.poll();
                boolean isBreak = false;
                if(current==null) 
                {
                    continue;
                }
                que.add(current);
                que.add(subRoot);
                while(!que.isEmpty()) 
                {
                    TreeNode left = que.poll();
                    TreeNode right = que.poll();
                    if(left==null&&right==null) 
                    {
                        continue;
                    }
                    else if(left==null&&right!=null) 
                    {
                        isBreak = true;
                        break;
                    }
                    else if(left!=null&&right==null) 
                    {
                        isBreak = true;
                        break;
                    }
                    else if(left.val!=right.val) 
                    {
                        isBreak = true;
                        break;
                    }

                    que.add(left.left);
                    que.add(right.left);
                    que.add(left.right);
                    que.add(right.right);
                }
                if (!isBreak)
                {
                    return true;
                }
                mainQ.add(current.left);
                mainQ.add(current.right);
            }
            return false;
        }
    }