另一棵树的子树

572. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10⁴ <= root.val <= 10⁴
-10⁴ <= subRoot.val <= 10⁴

相似题目

统计同值子树

出现次数最多的子树元素和

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isSubtree(TreeNode* root, TreeNode* subRoot) { } };

golang 解法, 执行用时: 7 ms, 内存消耗: 6.4 MB, 提交时间: 2024-08-04 11:41:52

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 代码逻辑同 104. 二叉树的最大深度
func getHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftH := getHeight(root.Left)
    rightH := getHeight(root.Right)
    return max(leftH, rightH) + 1
}

// 100. 相同的树
func isSameTree(p, q *TreeNode) bool {
    if p == nil || q == nil {
        return p == q // 必须都是 nil
    }
    return p.Val == q.Val &&
        isSameTree(p.Left, q.Left) &&
        isSameTree(p.Right, q.Right)
}

func isSubtree(root, subRoot *TreeNode) bool {
    hs := getHeight(subRoot)

    // 返回 node 的高度，以及是否找到了 subRoot
    var dfs func(*TreeNode) (int, bool)
    dfs = func(node *TreeNode) (int, bool) {
        if node == nil {
            return 0, false
        }
        leftH, leftFound := dfs(node.Left)
        rightH, rightFound := dfs(node.Right)
        if leftFound || rightFound {
            return 0, true
        }
        nodeH := max(leftH, rightH) + 1
        return nodeH, nodeH == hs && isSameTree(node, subRoot)
    }
    _, found := dfs(root)
    return found
}

cpp 解法, 执行用时: 20 ms, 内存消耗: 27.4 MB, 提交时间: 2024-08-04 11:41:34

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    // 代码逻辑同 104. 二叉树的最大深度
    int getHeight(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int left_h = getHeight(root->left);
        int right_h = getHeight(root->right);
        return max(left_h, right_h) + 1;
    }

    // 100. 相同的树
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr || q == nullptr) {
            return p == q; // 必须都是 nullptr
        }
        return p->val == q->val &&
               isSameTree(p->left, q->left) &&
               isSameTree(p->right, q->right);
    }

public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        int hs = getHeight(subRoot);

        // 返回 node 的高度，以及是否找到了 subRoot
        auto&& dfs = [&](auto&& dfs, TreeNode* node) -> pair<int, bool> {
            if (node == nullptr) {
                return {0, false};
            }
            auto [left_h, left_found] = dfs(dfs, node->left);
            auto [right_h, right_found] = dfs(dfs, node->right);
            if (left_found || right_found) {
                return {0, true};
            }
            int node_h = max(left_h, right_h) + 1;
            return {node_h, node_h == hs && isSameTree(node, subRoot)};
        };
        return dfs(dfs, root).second;
    }
};

java 解法, 执行用时: 2 ms, 内存消耗: 43.4 MB, 提交时间: 2024-08-04 11:41:05

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        int hs = getHeight(subRoot);
        return dfs(root, subRoot, hs).getValue();
    }

    // 代码逻辑同 104. 二叉树的最大深度
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.max(leftH, rightH) + 1;
    }

    // 100. 相同的树
    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            return p == q; // 必须都是 null
        }
        return p.val == q.val &&
               isSameTree(p.left, q.left) &&
               isSameTree(p.right, q.right);
    }

    // 返回 node 的高度，以及是否找到了 subRoot
    private Pair<Integer, Boolean> dfs(TreeNode node, TreeNode subRoot, int hs) {
        if (node == null) {
            return new Pair<>(0, false);
        }
        Pair<Integer, Boolean> left = dfs(node.left, subRoot, hs);
        Pair<Integer, Boolean> right = dfs(node.right, subRoot, hs);
        if (left.getValue() || right.getValue()) {
            return new Pair<>(0, true);
        }
        int nodeH = Math.max(left.getKey(), right.getKey()) + 1;
        return new Pair<>(nodeH, nodeH == hs && isSameTree(node, subRoot));
    }
}

python3 解法, 执行用时: 52 ms, 内存消耗: 16.7 MB, 提交时间: 2024-08-04 11:40:47

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # 代码逻辑同 104. 二叉树的最大深度
    def getHeight(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left_h = self.getHeight(root.left)
        right_h = self.getHeight(root.right)
        return max(left_h, right_h) + 1

    # 100. 相同的树
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q  # 必须都是 None
        return p.val == q.val and \
            self.isSameTree(p.left, q.left) and \
            self.isSameTree(p.right, q.right)

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        hs = self.getHeight(subRoot)

        # 返回 node 的高度，以及是否找到了 subRoot
        def dfs(node: Optional[TreeNode]) -> (int, bool):
            if node is None:
                return 0, False
            left_h, left_found = dfs(node.left)
            right_h, right_found = dfs(node.right)
            if left_found or right_found:
                return 0, True
            node_h = max(left_h, right_h) + 1
            return node_h, node_h == hs and self.isSameTree(node, subRoot)
        return dfs(root)[1]

javascript 解法, 执行用时: 62 ms, 内存消耗: 56 MB, 提交时间: 2024-08-04 11:40:04

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} s
 * @param {TreeNode} t
 * @return {boolean}
 */
var isSubtree = (s, t) => ( JSON.stringify(s).indexOf(JSON.stringify(t)) > -1 );

golang 解法, 执行用时: 12 ms, 内存消耗: 6.6 MB, 提交时间: 2021-07-13 16:51:36

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil {
        return false
    }
    return isSameTree(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

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

上一题

下一题

详情