Leetcode - subtree-of-another-tree

https://leetcode.com/problems/subtree-of-another-tree/

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4 
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

This can be solved by recursive. First, it should find a node from s which has the same value as the root of t. And then check whether the sub-tree is the same as t. For finding the subtree, it can be searched from  s.Left and s.Right with recursive method.

For checking the same tree, it can be solved here.

func isSubtree(s *TreeNode, t *TreeNode) bool {
    if s == nil && t != nil {
        return false
    }
    if s != nil && t == nil {
        return true
    }
    if s.Val == t.Val {
        result := isSameTree(s, t)
        if result {
            return true
        }
    }
    
    return isSubtree(s.Left, t) || isSubtree(s.Right, t)
}

func isSameTree(s *TreeNode, t *TreeNode) bool {
    if s == nil && t == nil {
        return true
    }
    if (s != nil && t == nil) || (s == nil && t != nil) {
        return false
    }
    if s.Val != t.Val {
        return false
    }

    return isSameTree(s.Left, t.Left) && isSameTree(s.Right, t.Right)
}

def is_subtree(s, t)
    if s == nil && t != nil
        return false
    end
    if s != nil && t == nil
        return true
    end
    if s.val == t.val
        if is_same_tree(s, t)
            return true
        end
    end
    
    return is_subtree(s.left, t) || is_subtree(s.right, t)
end

def is_same_tree(t1, t2)
    if (t1 != nil && t2 == nil) || (t1 == nil && t2 != nil)
        return false
    end
    if t1 == nil && t2 == nil
        return true
    end
    if t1.val != t2.val
        return false
    end
    return is_same_tree(t1.left, t2.left) && is_same_tree(t1.right, t2.right)
end

• 相关文章
• 全局相关文章