树的子结构「建议收藏」

全栈程序员站长

发布于 2022-07-07 18:58:16

1570

发布于 2022-07-07 18:58:16

文章被收录于专栏：全栈程序员必看全栈程序员必看

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

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

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

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一样的结构。

分析演示样例：

解决思路代码：

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

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);  // 递归推断左右子树
	}

}

測试代码：

// 进行測试
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 # #

执行结果：