[LeetCode] Subtree of Another Tree

greatwhole 发布于2019-08-15 15:59 / 1387人阅读

Problem

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

Example 1:
Given tree s:

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:

Given tree t:

   4
  / 
 1   2

Return false.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null) return true;
        if (s == null) return t == null;
        if (isSametree(s, t)) return true;
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    private boolean isSametree(TreeNode s, TreeNode t) {
        if (s == null) return t == null;
        if (t == null) return s == null;
        if (s.val != t.val) return false;
        return isSametree(s.left, t.left) && isSametree(s.right, t.right);
    }
}

专线服务私有云 another Subtree LeetCode git-subtree

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69361.html

LeetCode[333] Largest BST Subtree

摘要：复杂度思路考虑对于每一个节点来说，能组成的的。那么并且所以我们需要两个返回值，一个是这个是不是，另一个是当前的能组成的最大的值。代码这个能构成一个这个不能构成一个 LeetCode[333] Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary SearchTree (B...

WrBug 2019-08-14 15:03 评论0 收藏0
[LeetCode] Largest BST Subtree

Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it. Note: A subtree must include all ...

Youngdze 2019-08-14 14:55 评论0 收藏0
[LintCode/LeetCode] Binary Tree Pruning

Problem Binary Tree PruningWe are given the head node root of a binary tree, where additionally every nodes value is either a 0 or a 1. Return the same tree where every subtree (of the given tree) not...

rockswang 2019-08-16 12:37 评论0 收藏0
[LeetCode] 545. Boundary of Binary Tree

Problem Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate no...

newtrek 2019-08-16 14:26 评论0 收藏0
LeetCode 545. Boundary of Binary Tree 二叉树边界

摘要：二叉树边界题意高频题，必须熟练掌握。逆时针打印二叉树边界。解题思路根据观察，我们发现当为左边界时，也是左边界当为左边界时，为空，则也可以左边界。先加入左边，加入，然后得到两个子树加入，最后加入右边界。 LeetCode 545. Boundary of Binary Tree 二叉树边界Given a binary tree, return the values of its boun...

Astrian 2019-08-16 13:31 评论0 收藏0