49ms golang solution


  • 0
    S

    match conditions:

    1. same depth;
    2. fulfill condition 1, then all values are equal separately.

    firstly, i write a func getDepth to get the depth of each tree to solve condition 1;
    then judge if the same-depth two trees are identical by func sameTree to solve condition 2;
    lastly recur each subtree of each tree by func isSubtree

    all the three parts are recursive method.

    func isSubtree(s *TreeNode, t *TreeNode) bool {
        depT := getDepth(t)
        depS := getDepth(s)
        if depT == depS{
            return sameTree(t,s)
        }
        if depT > depS {
            return false
        }
        if isSubtree(s.Left,t){
            return true
        }
        return isSubtree(s.Right,t)
    }
    
    func sameTree(a,b *TreeNode) bool {
        if a != nil && b != nil {
            if a.Val == b.Val {
                return true && sameTree(a.Left,b.Left) && sameTree(a.Right,b.Right)
            }
        }else if a == nil && b == nil{
            return true
        }
        return false
    }
    
    func getDepth(root *TreeNode) int{
        if root == nil {
            return 0
        }
        left := getDepth(root.Left)
        right := getDepth(root.Right)
        if left>right {
            return 1+left
        }
        return 1+right
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.