7

LeetCode: 572. Subtree of Another Tree

 3 years ago
source link: https://mozillazg.com/2021/01/leetcode-572-subtree-of-another-tree.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目

原题地址：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)
        )

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK