二叉树中的列表

weblog 183 0 0

leetcode1637题(中等

原链接:https://leetcode-cn.com/problems/linked-list-in-binary-tree/

问题描述

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中,存在一条一直向下的路径,且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,那么请你返回 True ,否则返回 False 。

一直向下的路径的意思是:从树中某个节点开始,一直连续向下的路径。

示例1

输入:head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出:true
解释:树中蓝色的节点构成了与链表对应的子路径。

示例2

输入:head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

输出:true

示例3

输入:head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出:false
解释:二叉树中不存在一一对应链表的路径。

解题思路

枚举,递归,深度优先搜索dfs

枚举二叉树得所有节点,从某节点开始递归以该节点为头节点得子树(使用深度优先搜索算法)。递归过程中如果满足链表中所有节点都能和该子树的节点对应返回true,否则返回false。

不满足条件的情况可能有:

  • 1.二叉树到达叶子节点,但是链表没有到最后一个节点
  • 2.二叉树和链表对应的节点的值不相等

代码(java)

/**
 * 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(root.val!=head.val){
            return false;
        }
        return dfs(head.next,root.left)||dfs(head.next,root.right);
    }
}
猜你喜欢
official 204 。本题,一棵高度平衡定义为:一个每个节点左右两个子高度差绝对值不超过1。示例1案例输入:root=[3,9,20,null,null,15,7],输出:true示例2案例输入:r
official 211 述给定一个搜索根节点root,和一个整数k,请你设计一个算法查找其第k个最小元素(从1开始计数)。示例1输入:root=[3,1,4,null,2],k=1 输出:1示例2输入:root=[5
数据结构与算法 6348 题目:判断下方两棵右方是否为左方例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
official 206 leetcode第257题(简单)原链接:https://leetcode-cn.com/problems/binary-tree-paths/题目描述给定一个,返回所有从根节点到叶子节点
数据结构与算法 4153 整理遍历-(递归法)和(非递归法)-笔记先序遍历、序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//数据域
数据结构与算法 4754 试题描述:思路:用数组示完全,用先序遍历方式遍历每一层节点,用一个数组储存每一层和,因为数据规模小于100000所以用一个容量为17数组即可。计算完每一层和,再比较层数最小之和最大
数据结构与算法 3231 在关于多种算法都用到了旋转来使保持相对平衡,比如avl,红黑等...1.左旋(pivot为旋转心点)2.来个动图3.代码演示:/** *左旋 *p为旋转心点
数据结构与算法 2478 转载:https://www.cnblogs.com/willwu/p/6007555.html1.定义是一种数据结构,它是由n(n=1)个有限节点组成一个具有层次关系集合。把它叫做“”是
目录
祝愿神州十三飞行乘组平安归来