文档章节

判断是否为一棵树的子树 Subtree of Another Tree

叶枫啦啦
 叶枫啦啦
发布于 2017/08/11 19:50
字数 438
阅读 6
收藏 0

问题:

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.

解决:

① 给定两个树s和t,判断t是否是s的一个子树。这里s的子树是指,一个树由s中的一个节点及其所有子节点组成,s也可以是自己本身的一个子树

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

② 在discuss中看到以下解法

public class Solution { // 16ms
    public boolean isSubtree(TreeNode s, TreeNode t) {
        return isSubtree(s, t, true);
    }
    private boolean isSubtree(TreeNode s, TreeNode t, boolean isHead) {
        if (s == null && t == null) return true;
        if (s == null || t == null || (s.val != t.val && !isHead)) return false; //isHead表示是否以当前节点为根节点比较子树的
        if (s.val == t.val) {
            boolean left = isSubtree(s.left, t.left, false);
            boolean right = isSubtree(s.right, t.right, false);
            if (left && right) {
                return true;
            } else {
                left = isSubtree(s.left, t, true);
                right = isSubtree(s.right, t, true);
                return left || right;
            }
        } else {
            boolean left = isSubtree(s.left, t, true);
            boolean right = isSubtree(s.right, t, true);
            return left || right;
        }
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
LeetCode572. 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 no......

dby_freedom
2018/12/18
0
0
LeetCode 98. Validate Binary Search Tree (有效二叉搜索树)

原题 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less ......

dby_freedom
2018/12/03
0
0
海量数据:判断一棵树是否为另一棵树的子树

T1是一棵含有几百万个节点的树,T2含有几百个节点。判断T2是否是T1 的子树。 首先考虑小数据量的情况,可以根据树的前序和中序遍历所得的字符串,来通过判断T2生成的字符串是否是T1字符串的子...

一贱书生
2016/11/18
92
0
验证二叉搜索树

原题   Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:   The left subtree of a node contains only nodes with k......

一贱书生
2016/12/20
8
0
[LeetCode] Count Univalue Subtrees 计数相同值子树的个数

/ 1 5/ 5 5 5 public: }; 解法二: class Solution {public: }; 我们还可以变一种写法,让递归函数直接返回以当前节点为根的相同值子树的个数,然后参数里维护一个引用类型的布尔变量,表示以...

机器的心脏
2017/12/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Handler简解

Handler 这里简化一下代码 以便理解 Handler不一定要在主线程建 但如Handler handler = new Handler(); 会使用当前的Looper的, 由于要更新UI 所以最好在主线程 new Handler() { mLooper = Lo...

shzwork
19分钟前
2
0
h5获取摄像头拍照功能

完整代码展示: <!DOCTYPE html> <head> <title>HTML5 GetUserMedia Demo</title> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum......

诗书易经
22分钟前
2
0
正向代理和反向代理

文章来源 运维公会:正向代理和反向代理 1、正向代理 (1)服务对象不同 正向代理服务器的服务对象是客户端,可以将客户端和代理服务器看作一个整体。 (2)配置方法不同 需要在客户端配置代...

运维团
38分钟前
3
0
5个避免意外论文重复率高的方法

即使你不是故意抄袭,但你可能在无意中抄袭了别人的论文, 这个叫做意外抄袭,它可能正发生在你身上,如果你不熟悉学术 道德规范,这里将告诉你5个基本的方法来避免意外抄袭。 Tip1 熟悉其他...

论文辅导员
40分钟前
3
0
Maven通过profiles标签读取不同的配置

<profiles> <profile> <id>dev</id> <properties> <profiles.active>dev</profiles.active> </properties> ......

时刻在奔跑
45分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部