LeetCode: 572. 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.

Example 2:

Given tree s:

    3
   / \
  4   5
 / \
1   2
   /
  0

Given tree t:

  4
 / \
1   2

Return false.

解法

前序遍历这两个树，生成两个各自子节点组成的结果字符串，然后判断两个字符串是否存在包含关系，如果是的话，说明就是子树关系。

这个方法的 Python 代码类似下面这样:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSubtree(self, s, t):
        s_nodes_str = self._preorder(s, True)
        t_nodes_str = self._preorder(t, True)
        return t_nodes_str in s_nodes_str

    def _preorder(self, root, is_left):
        if root is None:
            if is_left:
                return 'left_none'
            else:
                return 'right_none'

        # 开头和结尾的 # 以及 left_none 和 right_none 是为了便于验证树的结构是否一致
        return '#{}-{}-{}#'.format(
            root.val,
            self._preorder(root.left, True),
            self._preorder(root.right, False)
        )

Comments