thảo luận Leetcode mỗi ngày

class Solution {
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int m, n;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;

        m = matrix.length;
        n = matrix[0].length;
        int ans = 0;

        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dfs(i, j, matrix, dp));
            }
        }

        return ans;
    }

    private int dfs(int r, int c, int[][] matrix, int[][] dp) {
        if (dp[r][c] > 0) return dp[r][c];

        int max = 1;

        for (int[] d : dirs) {
            int nextR = r + d[0];
            int nextC = c + d[1];

            if (nextR >= 0 && nextR < m && nextC >= 0 && nextC < n && matrix[nextR][nextC] > matrix[r][c]) {
                max = Math.max(max, 1 + dfs(nextR, nextC, matrix, dp));
            }
        }

        dp[r][c] = max;

        return dp[r][c];
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        if not root:  
            return False
        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
    def dfs(self,head: ListNode, root: TreeNode) -> bool:
            if not head:  
                return True
            if not root:  
                return False
            if root.val != head.val:  
                return False
            return self.dfs(head.next, root.left) or self.dfs(head.next, root.right)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        def travelList(node, pointer):
            if not pointer:
                return True
            
            if not node or node.val != pointer.val:
                return False
            return travelList(node.left, pointer.next) or travelList(node.right, pointer.next)
        def travelNode(node):
            if node == None:
                return False
    
            if node.val == head.val and travelList(node, head):
                return True
            
            return travelNode(node.left) or travelNode(node.right)
        return travelNode(root)

class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode tNode = queue.poll();
            if(tNode.val == head.val){
                if(dfs(head, tNode)) return true;
            }
            if(tNode.left!= null) queue.offer(tNode.left);
            if(tNode.right!=null) queue.offer(tNode.right);
        }
        return false;
    }
    public boolean dfs(ListNode node, TreeNode tNode){
        if(node!=null && tNode == null) return false;
        else if(node==null) return true;
        else if(node.val == tNode.val){
            return dfs(node.next,tNode.left) || dfs(node.next, tNode.right);
        }
        else return false;
    }
}

class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if(root==null) return false;
        if(root.val == head.val){
            if(dfs(head, root)) return true;
        }
        return isSubPath(head, root.left)|| isSubPath(head, root.right);
    }
    public boolean dfs(ListNode node, TreeNode tNode){
        if(node==null) return true;
        else if(node!=null && tNode == null) return false;
        else if(node.val == tNode.val){
            return dfs(node.next,tNode.left) || dfs(node.next, tNode.right);
        }
        else return false;
    }
}

impl Solution {
    fn has_path_from_root(head_of_path: &Option<Box<ListNode>>, root: &Option<Rc<RefCell<TreeNode>>>) -> bool {
        match (head_of_path, root) {
            (None, _) => true,
            (_, None) => false,
            (Some(head), Some(root)) => {
                if head.val != root.borrow().val {
                    false
                } else {
                    Self::has_path_from_root(&head.next, &root.borrow().left)
                        || Self::has_path_from_root(&head.next, &root.borrow().right)
                }
            }
        }
    }

    fn is_sub_path_borrow(head: &Option<Box<ListNode>>, root: &Option<Rc<RefCell<TreeNode>>>) -> bool {
        if Self::has_path_from_root(head, root) {
            true
        } else {
            match root {
                None => false,
                Some(root) => {
                    Self::is_sub_path_borrow(head, &root.borrow().left)
                        || Self::is_sub_path_borrow(head, &root.borrow().right)
                }
            }
        }
    }

    pub fn is_sub_path(head: Option<Box<ListNode>> root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        Self::is_sub_path_borrow(&head, &root)
    }
}