上海做设计公司网站,兰州市城乡和住房建设局网站,洛阳信息网,目前比较新的网站建设技术1367.二叉树中的链表 方法#xff1a;枚举
枚举二叉树中的每个节点为起点往下的路径是否与链表相匹配的路径#xff0c;为了判断是否匹配设计了一个递归函数dfs(root,head),其中root表示当前匹配到的二叉树节点#xff0c;head表示当前匹配到的链表节点#xff0c;整个函数…1367.二叉树中的链表 方法枚举
枚举二叉树中的每个节点为起点往下的路径是否与链表相匹配的路径为了判断是否匹配设计了一个递归函数dfs(root,head),其中root表示当前匹配到的二叉树节点head表示当前匹配到的链表节点整个函数返回布尔值表示是否有一条该节点往下的路径与head节点开始的链表匹配如匹配返回true否则返回false一共有四种情况
链表已经全部匹配完匹配成功返回true二叉树访问到了空节点匹配失败返回false当前匹配的二叉树上的节点的值与链表节点的值不相等匹配失败返回false前三种情况都不满足说明匹配成功了一部分需要继续递归处理先调用dfs(root.left,head.next)如果返回结果是false说明没有匹配的路径需要继续在右子树中匹配继续递归调用函数
接下来就是枚举从根节点开始如果当前匹配成功就直接返回true否则继续找它的左儿子和右儿子是否满足
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
/*** 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;* }* }*/
class Solution {public boolean isSubPath(ListNode head, TreeNode root) {if(root null) return false;return dfs(head,root) || isSubPath(head,root.left) || isSubPath(head,root.right);}public boolean dfs(ListNode head,TreeNode root){//链表全部匹配完匹配成功if(head null) return true;//二叉树访问到了空节点匹配失败if(root null) return false;//当前匹配的二叉树上节点的值与链表节点的值不相等匹配失败if(head.val ! root.val) return false;return dfs(head.next,root.left) || dfs(head.next,root.right);}
}
