前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >树的子结构「建议收藏」

树的子结构「建议收藏」

作者头像
全栈程序员站长
发布2022-07-07 18:58:16
1550
发布2022-07-07 18:58:16
举报

大家好,又见面了,我是全栈君。

来自《剑指offer》的面试题18。

题目:输入两棵二叉树A和B,推断B是不是A的子结构。二叉树节点定义例如以下:

代码语言:javascript
复制
public class TreeNode {
	int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}

思路分析:

首先,在Tree1中找到和Tree2的根节点的值一样的结点R。

然后,再推断Tree1中以R为根结点的子树是不是包括和Tree2一样的结构。

分析演示样例:

树的子结构「建议收藏」
树的子结构「建议收藏」

解决思路代码:

这里两处推断均使用了递归。详见代码。

代码语言:javascript
复制
public class Solution {
	public boolean HasSubtree(TreeNode root1, TreeNode root2) { // 在Tree1中查找是否有Tree2的根节点(实际上就是树的遍历)
		boolean result = false;
		if (root1 != null && root2 != null) {  // 边界条件的检查
			if (root1.val == root2.val) {
				result = DosTree1HasTree2(root1, root2);
			}
			if (!result) {
				result = HasSubtree(root1.left, root2);
			}
			if (!result) {
				result = HasSubtree(root1.right, root2);
			}
		}
		return result;
	}

	public boolean DosTree1HasTree2(TreeNode root1, TreeNode root2) {  // 推断Tree1中以R为根节点的子树是不是和树B具有同样的结构(即左右子树是否同样)
		if (root2 == null) {  // 递归终止条件到达了Tree1或Tree2的叶节点。
			return true;
		}
		if (root1 == null) {
			return false;
		}

		if (root1.val != root2.val) {
			return false;
		}
		return DosTree1HasTree2(root1.left, root2.left)
				&& DosTree1HasTree2(root1.right, root2.right);  // 递归推断左右子树
	}

}

測试代码:

代码语言:javascript
复制
// 进行測试
public class Main {
	Scanner scanner = new Scanner(System.in);
	
	public TreeNode createTree(TreeNode root) {
		String val = scanner.next();
		if (val.equals("#")) {
			return null;
		}
		root = new TreeNode(Integer.parseInt(val));
		root.left = createTree(root.left);
		root.right = createTree(root.right);
		return root;
	}
	public static void main(String[] args) {
		TreeNode root1 = null;
		TreeNode root2 = null;
		Main testMain = new Main();
		Solution testSolution = new Solution();
		boolean result = false;
		
		System.out.println("Create Tree 1:");
		root1 = testMain.createTree(root1);
		System.out.println("Create Tree 2:");
		root2 = testMain.createTree(root2);
		result = testSolution.HasSubtree(root1, root2);
		System.out.println("The result is: " + result);
	}
}

測试数据为: 8 8 9 # # 2 4 # # 7 # # 7 # # 8 9 # # 2 # #

执行结果:

树的子结构「建议收藏」
树的子结构「建议收藏」

牛客网測试地址:http://www.nowcoder.com/books/coding-interviews/6e196c44c7004d15b1610b9afca8bd88?rp=1

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116419.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年1月2,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档