LeetCode——572. 另一颗树的子树

通过万岁！！！

• 题目：给你两棵树，然后问subRoot是不是root的子树。也就是root某个节点的所有孩子节点在值和结构上完全与subRoot相同。
• 思路：我的思路比较简单，就是遍历root，遇到root中节点值与subRoot的根节点相同的，就去判断下从root的这个节点开始，下面部分是不是与subRoot相同。值得注意的是，因为要求值和结构完全相同，所以遍历的顺序要一致。此外，如果我们发现了subRoot是root的子树的时候，要停止遍历。
• 技巧：树的遍历

java代码

class Solution {boolean ret = false;public boolean isSubtree(TreeNode root, TreeNode subRoot) {preorderByRecursion(root, subRoot);return ret;}/*** 前序遍历root这个树** @param root* @param subRoot*/private void preorderByRecursion(TreeNode root, TreeNode subRoot) {if (root == null || ret) return;if (root.val == subRoot.val) {ret = traverseTree(root, subRoot);if (ret) {return;}}preorderByRecursion(root.left, subRoot);preorderByRecursion(root.right, subRoot);}/*** 遍历两个树，看下结构和值是不是相同** @param root* @param subRoot* @return*/private boolean traverseTree(TreeNode root, TreeNode subRoot) {if (subRoot == null && root == null) {return true;} else if (root == null) {return false;} else if (subRoot == null) {return false;} else {if (root.val == subRoot.val) {boolean left = traverseTree(root.left, subRoot.left);if (left) {return traverseTree(root.right, subRoot.right);}return false;} else {return false;}}}
}

• 总结：题目不是特别难，但是好久不写递归了，有点生疏。其实我们可以找到拿到两棵树的中序和后续的字符串，然后判断下subRoot字符串是不是的包含在root的字符串之内，但是需要中序和后序都满足，不过我没有测试。