huzecong的解法。
其实两个递归方法，每个都字如其名。
checkPath: 已经找到了head和root两个对应的起点，都有next,然后对应都往下找；isSubPath: 首先调用checkPath看当前head能不能是对应的path的一部分，如果不能就看Tree中的部分能不能；i.e. head不动，root往下.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
if (checkPath(head, root)) return true;
if (root.left != null && isSubPath(head, root.left)) return true;
if (root.right != null && isSubPath(head, root.right)) return true;
return false;
}
public boolean checkPath(ListNode head, TreeNode root) {
if (head.val != root.val) return false;
if (head.next == null) return true;
if (root.left != null && checkPath(head.next, root.left)) return true;
if (root.right != null && checkPath(head.next, root.right)) return true;
return false;
}
}
|
关于这个问题，实际上可以延伸出来另一个问题，判断tree2是不是tree1的子树:
- 递归的思想，如果根节点相同，继续判断左右子树是否相同
- 根节点不同，就递归判断
tree1的左右子树和子树
1
2
3
4
5
6
| public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 && root2) {
if (isPart(root1, root2)) return true;
if (isPart(root1.left, root2)) return true;
if (isPart(root1.right, root2)) return true;
}
return false;
}
public boolean isPart(TreeNode root1, TreeNode root2) {
if (root2 == null) return true;
if (root1 == null) return false;
if (root1.val == root2.val) {
return isPart(root1.left, root2.left) && isPart(root1.right, root2.right);
}
return false;
}
|
总结
其实入口函数只是更上层抽象调用worker递归函数的一个东西，真正完整递归调用的逻辑都在dfs递归调用中