572. 另一个树的子树

骑猪看日落 2023-10-05 21:07 6阅读 0赞

给定两个非空二叉树 **s** 和 **t**，检验 **s** 中是否包含和 **t** 具有相同结构和节点值的子树。**s** 的一个子树包括 **s** 的一个节点和这个节点的所有子孙。**s** 也可以看做它自身的一棵子树。

**示例 1:**  
给定的树 s:

3
        / \
       4   5
      / \
     1   2

给定的树 t：

4 
      / \
     1   2

返回 **true**，因为 t 与 s 的一个子树拥有相同的结构和节点值。

**示例 2:**  
给定的树 s：

3
        / \
       4   5
      / \
     1   2
        /
       0

给定的树 t：

4
      / \
     1   2

返回 **false**。

package Solution572;
    
    // 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;
    	}
    }

package Solution572;
    
    class Solution {
    	public boolean isSameTree(TreeNode p, TreeNode q) {
    		if (p == null && q == null) {
    			return true;
    		}
    
    		if ((p == null || q == null) || p.val != q.val) {
    			return false;
    		}
    
    		if (!isSameTree(p.left, q.left)) {
    			return false;
    		}
    
    		if (!isSameTree(p.right, q.right)) {
    			return false;
    		}
    		return true;
    	}
    
    	public boolean isSubtree(TreeNode s, TreeNode t) {
    		if (s == null) {
    			return false;
    		}
    		return isSameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    	}
    
    	/* This function returns true if S is a subtree of T, otherwise false */
    
    	public static void main(String args[]) {
    		Solution sol = new Solution();
    		TreeNode root1;
    		TreeNode root2;
    
    		// TREE 1
    		/*
    		 * Construct the following tree 26 / \ 10 3 / \ \ 4 6 3 \ 30
    		 */
    
    		root1 = new TreeNode(26);
    		root1.right = new TreeNode(3);
    		root1.right.right = new TreeNode(3);
    		root1.left = new TreeNode(10);
    		root1.left.left = new TreeNode(4);
    		root1.left.left.right = new TreeNode(30);
    		root1.left.right = new TreeNode(6);
    
    		// TREE 2
    		/*
    		 * Construct the following tree 10 / \ 4 6 \ 30
    		 */
    
    		root2 = new TreeNode(10);
    		root2.right = new TreeNode(6);
    		root2.left = new TreeNode(4);
    		root2.left.right = new TreeNode(30);
    
    		if (sol.isSubtree(root1, root2))
    			System.out.println("Tree 2 is subtree of Tree 1 ");
    		else
    			System.out.println("Tree 2 is not a subtree of Tree 1");
    	}
    
    }