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

function getDirections(root: TreeNode | null, start: number, dest: number): string {
    const findLca = (node: TreeNode, u: number, v: number) => {
        if (!node) return null;
        if (node.val === u || node.val === v) return node;
        const l = findLca(node.left, u, v);
        const r = findLca(node.right, u, v);
        if (!l) return r;
        else if (!r) return l;
        else return node;
    }
    const go = (node: TreeNode, val: number, res = '') => {
        if (!node) return '';
        if (node.val === val) return res;
        return go (node.left, val, res + 'L') + go (node.right, val, res + 'R')
    }

    const lca = findLca(root, start, dest);
    const s = go(lca, start), d = go(lca, dest);
    return 'U'.repeat(s.length) + d
};

// Problem: https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/
class Solution {
    func getDirections(_ root: TreeNode?, _ startValue: Int, _ destValue: Int) -> String {
        var startPath: String = findPath(root, startValue) ?? ""
        var destPath: String = findPath(root, destValue) ?? ""

        while !startPath.isEmpty  && !destPath.isEmpty {
            if startPath[startPath.startIndex] == destPath[destPath.startIndex] {
                startPath.removeFirst()
                destPath.removeFirst()
            } else {
                break
            }
        }
        return String(repeating: "U", count: startPath.count) + destPath
    }
    
    func findPath(_ root: TreeNode?, _ value: Int) -> String? {
        guard let root else { return nil }

        if root.val == value {
            return ""
        }
        
        if let path = findPath(root.right, value) {
            return "R" + path
        }
        
        if let path = findPath(root.left, value) {
            return "L" + path
        }
        return nil
    }
}

class Solution {
    func getDirections(_ root: TreeNode?, _ startValue: Int, _ destValue: Int) -> String {
        var startPath = ""
        var destPath = ""
        
        func dfs(_ tree: TreeNode?, path: inout String) {
            guard let tree else { return }
            if tree.val == startValue {
                startPath = path
            } else if tree.val == destValue {
                destPath = path
            }
            if !startPath.isEmpty && !destPath.isEmpty {
                return
            }
            path.append("L")
            dfs(tree.left, path: &path)
            _ = path.popLast()
            
            path.append("R")
            dfs(tree.right, path: &path)
            _ = path.popLast()
        }
        var path = ""
        dfs(root, path: &path)
        
        let common = startPath.commonPrefix(with: destPath)
        var result = String(repeating: "U", count: startPath.count - common.count)
        result += String(destPath.dropFirst(common.count))
        
        return result
    }
}

class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        StringBuilder startPath = new StringBuilder();
        StringBuilder destPath = new StringBuilder();
        findNode(root, startValue, startPath);
        findNode(root, destValue, destPath);

        while (startPath.length() > 0 && destPath.length() > 0
                && startPath.charAt(startPath.length() - 1) == destPath.charAt(destPath.length() - 1)) {
            startPath.setLength(startPath.length() - 1);
            destPath.setLength(destPath.length() - 1);
        }
        int len = startPath.length();
        startPath = new StringBuilder();
        for (int i = 0; i < len; i++) {
            startPath.append('U');
        }
        destPath.reverse();
        return startPath.toString() + destPath.toString();
    }

   public boolean findNode(TreeNode root, int val,StringBuilder path){
        if(root.val == val ) return true;
        if(root.left !=null && findNode(root.left,val, path)) path.append('L');
        else if(root.right !=null && findNode(root.right,val, path)) path.append('R');
        return path.length()>0;
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} startValue
 * @param {number} destValue
 * @return {string}
 */
var getDirections = function (root, startValue, destValue) {
    function getAdjacencyList() {
        const g = {};

        function dfsTree(currentNode) {
            if (!currentNode) {
                return;
            }

            if (currentNode.left) {
                if (!g[currentNode.val]) g[currentNode.val] = [];
                if (!g[currentNode.left.val]) g[currentNode.left.val] = [];
                
                g[currentNode.val].push([currentNode.left.val, 'L']);
                g[currentNode.left.val].push([currentNode.val, 'U']);

                dfsTree(currentNode.left);
            }

            if (currentNode.right) {
                if (!g[currentNode.val]) g[currentNode.val] = [];
                if (!g[currentNode.right.val]) g[currentNode.right.val] = [];
                
                g[currentNode.val].push([currentNode.right.val, 'R']);
                g[currentNode.right.val].push([currentNode.val, 'U']);

                dfsTree(currentNode.right);
            }
        }

        dfsTree(root);

        return g;
    }

    const graph = getAdjacencyList();

    function bfs() {
        const result = [];
        const visitedVertex = new Set();
        const queue = [[startValue, []]];

        while (queue.length) {
            const [vertex, path] = queue.shift();
            if (vertex === destValue) {
                return path;
            }

            visitedVertex.add(vertex);

            for (const [neighbor, step] of graph[vertex]) {
                if (!visitedVertex.has(neighbor)) {
                    queue.push([neighbor, path + step]);
                }
            }
        }

        return ''
    }


    return bfs();
};

impl Solution {
    pub fn get_directions(
        root: Option<Rc<RefCell<TreeNode>>>,
        start_value: i32,
        dest_value: i32,
    ) -> String {
        fn path_to_node(
            root: &Rc<RefCell<TreeNode>>,
            node_value: i32,
            current_path: &mut Vec<char>,
        ) -> Option<Vec<char>> {
            let node = root.as_ref().borrow();
            if node.val == node_value {
                return Some(current_path.to_owned())
            }
            
            if let Some(left) = &node.left {
                current_path.push('L');
                let path = path_to_node(left, node_value, current_path);
                if path.is_some() {
                    return path;
                }
                current_path.pop();
            }

            if let Some(right) = &node.right {
                current_path.push('R');
                let path = path_to_node(right, node_value, current_path);
                if path.is_some() {
                    return path;
                }
                current_path.pop();
            }

            None
        }

        let root = unsafe { root.unwrap_unchecked() };
        let (path_to_start, path_to_dest) = unsafe {
            (
                path_to_node(&root, start_value, &mut vec![]).unwrap_unchecked(),
                path_to_node(&root, dest_value, &mut vec![]).unwrap_unchecked(),
            )
        };

        let mut i = 0;
        while i < usize::min(path_to_start.len(), path_to_dest.len()) {
            if unsafe { path_to_start.get_unchecked(i) != path_to_dest.get_unchecked(i) } {
                break;
            }
            i += 1;
        }
        let path = [&vec!['U'; path_to_start.len() - i], &path_to_dest[i..]].concat();
        path.into_iter().collect()
    }
}

# 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 getDirections(self, root: Optional[TreeNode], s: int, d: int) -> str:
        # Approach 1 : Graph
        # graph = defaultdict(list)
        # q = deque([root])
        
        # while q:
        #     node = q.popleft()
        #     if node.left:
        #         graph[node.val].append([node.left.val, "L"])
        #         graph[node.left.val].append([node.val, "U"])
        #         q.append(node.left)
        #     if node.right:
        #         graph[node.val].append([node.right.val, "R"])
        #         graph[node.right.val].append([node.val, "U"])
        #         q.append(node.right)
        
        # final_q = deque([(s,"")])
        # visited = set()
        # while final_q:
        #     curr, path = final_q.popleft()
        #     if curr in visited:
        #         continue
        #     if curr == d:
        #         return path
        #     visited.add(curr)
        #     for neighbor, di in graph[curr]:
        #         final_q.append((neighbor, path + di))
        # return ""
        # Approach 2 : Find common
        def find_path(end) -> str:
            q = deque([(root,"")])
            while q:
                node, curr = q.popleft()
                if node.val == end:
                    return curr
                if node.left:
                    q.append((node.left, curr + "L"))
                if node.right:
                    q.append((node.right, curr + "R"))
            return ""
        
        root_to_start = find_path(s)
        root_to_end = find_path(d)
        n1 = len(root_to_start)
        n2 = len(root_to_end)
        idx1 = idx2 = 0
        while idx1 < n1 and idx2 < n2 and root_to_start[idx1] == root_to_end[idx2]:
            idx1 += 1
            idx2 += 1
        ans = ""
        if idx1 < n1 :
            ans += "U" * (n1 - idx1)
        if idx2 < n2 :
            ans += root_to_end[idx2:]
        return ans

class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        startPath = ''
        endPath = ''
        def findPath(root, path):
            nonlocal startPath, endPath
            if root.val == startValue:
                startPath = ''.join(path)
            elif root.val == destValue:
                endPath = ''.join(path)
            if startPath and endPath:
                return
            if root.left:
                path.append('L')
                findPath(root.left, path)
                path.pop()
            if root.right:
                path.append('R')
                findPath(root.right, path)
                path.pop()
        
        findPath(root, [])
        minPathLen, i = min(len(startPath), len(endPath)), 0
        while i < minPathLen and startPath[i] == endPath[i]:
            i += 1
        return (len(startPath) - i) * 'U' + endPath[i:]

var getDirections = function(root, startValue, destValue) {
    const findLCA = (node, p, q) => {
        if (!node) return null;
        if (node.val == p || node.val == q) return node;
        const left = findLCA(node.left, p, q);
        const right = findLCA(node.right, p, q);
        if (left && right) return node;
        if (!left) return right;
        if (!right) return left;
        return null;
    }

    const findPath = (startNode, endValue, paths) => {
        if (!startNode) return false;
        if (startNode.val == endValue) return true;

        paths.push("L");
        if (startNode.left && findPath(startNode.left, endValue, paths)) return true;
        paths.pop();

        paths.push("R");
        if (startNode.right && findPath(startNode.right, endValue, paths)) return true;
        paths.pop();

        return false;
    }

    const lca = findLCA(root, startValue, destValue);

    const lcaToStart = [];
    findPath(lca, startValue, lcaToStart);
    const lcaToDest = [];
    findPath(lca, destValue, lcaToDest);

    const res = [];
    for (let i = 0; i < lcaToStart.length; i++) {
        res.push('U');
    }
    for (const step of lcaToDest) {
        res.push(step);
    }
    return res.join('');
};

class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        String startPath = dfs(root, startValue, new Stack<String>());
        String destPath = dfs(root, destValue, new Stack<String>());
        int min = Math.min(startPath.length(), destPath.length());
        int n = startPath.length(), m = destPath.length();

        int idx = 0;

        while (idx < min && startPath.charAt(idx) == destPath.charAt(idx)) {
            idx++;
        }

        return "U".repeat(n - idx) + destPath.substring(idx, m);
    }

    private String dfs(TreeNode node, int target, Stack<String> stack) {
        if (node == null) return "";

        if (node.val == target) {
            StringBuilder ans = new StringBuilder();

            for (String str: stack) {
                ans.append(str);
            }

            return ans.toString();
        }
        
        stack.push("L");
        String left = dfs(node.left, target, stack);
        stack.pop();
        stack.push("R");
        String right = dfs(node.right, target, stack);
        stack.pop();

        return left + right;
    }
}

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn get_directions(root: Option<Rc<RefCell<TreeNode>>>, start_value: i32, dest_value: i32) -> String {
        type Node = Rc<RefCell<TreeNode>>;

        enum Found {
            Start,
            Dest,
            Both
        }

        fn recurse(node: Option<&Node>, start: i32, dest: i32) -> Option<(Found, Vec<u8>)> {
            if node.is_none() {
                return None;
            }

            let node = node.unwrap();

            let (mut found_start, mut found_dest) = (None, None);

            if node.borrow().val == start {
                found_start = Some((Found::Start, vec![]));
            }

            if node.borrow().val == dest {
                found_dest = Some((Found::Dest, vec![]));
            }

            let mut found_left = recurse(node.borrow().left.as_ref(), start, dest);

            match found_left {
                found_left @ Some((Found::Both, _)) => return found_left,
                Some((Found::Start, mut instructions)) => {
                    instructions.push(b'U');

                    found_start = Some((Found::Start, instructions));
                },
                Some((Found::Dest, mut instructions)) => {
                    instructions.push(b'L');

                    found_dest = Some((Found::Dest, instructions));
                },
                None => ()
            }

            let mut found_right = recurse(node.borrow().right.as_ref(), start, dest);

            match found_right {
                found_right @ Some((Found::Both, _)) => return found_right,
                Some((Found::Start, mut instructions)) => {
                    instructions.push(b'U');

                    found_start = Some((Found::Start, instructions));
                },
                Some((Found::Dest, mut instructions)) => {
                    instructions.push(b'R');

                    found_dest = Some((Found::Dest, instructions));
                },
                None => ()
            }

            match (found_start, found_dest) {
                (Some((Found::Start, mut start_instructions)), Some((Found::Dest, mut dest_instructions))) => {
                    dest_instructions.reverse();
                    start_instructions.append(&mut dest_instructions);

                    Some((Found::Both, start_instructions))
                },
                (Some((Found::Dest, mut dest_instructions)), Some((Found::Start, mut start_instructions))) => {
                    dest_instructions.reverse();
                    start_instructions.append(&mut dest_instructions);

                    Some((Found::Both, start_instructions))
                },
                (found_start, None) => found_start,
                (None, found_dest) => found_dest,
                _ => None
            }
        }

        match recurse(root.as_ref(), start_value, dest_value) {
            Some((Found::Both, instructions)) => {
                unsafe { String::from_utf8_unchecked(instructions) }
            },
            _ => "".to_owned()
        }
    }
}

function getDirections(root: TreeNode | null, startValue: number, destValue: number): string {
    if (!root) return "";

    function findPath(node: TreeNode | null, target: number, path: string[]): boolean {
        if (!node) return false;
        if (node.val === target) return true;

        if (findPath(node.left, target, path)) {
            path.push('L');
            return true;
        }
        if (findPath(node.right, target, path)) {
            path.push('R');
            return true;
        }

        return false;
    }

    const startPath: string[] = [];
    const destPath: string[] = [];

    findPath(root, startValue, startPath);
    findPath(root, destValue, destPath);

    while (startPath.length > 0 && destPath.length > 0 &&
           startPath[startPath.length - 1] === destPath[destPath.length - 1]) {
        startPath.pop();
        destPath.pop();
    }

    return 'U'.repeat(startPath.length) + destPath.reverse().join('');
}

use std::rc::Rc;
use std::cell::RefCell;

type Node = Rc<RefCell<TreeNode>>;

impl Solution {
    pub fn lowest_common_ancestor(root: Option<Node>, p: Option<Node>, q: Option<Node>) -> Option<Node> {
        let p = p.unwrap().borrow().val;
        let q = q.unwrap().borrow().val;

        enum Found {
            P,
            Q,
            Both
        }

        fn recurse(node: Option<&Node>, p: i32, q: i32) -> Option<(Found, Node)> {
            if node.is_none() {
                return None;
            }

            let node = node.unwrap();
            let val = node.borrow().val;

            let (mut found_p, mut found_q) = (None, None);

            if val == p {
                found_p = Some((Found::P, node.clone()));
            }

            if val == q {
                found_q = Some((Found::Q, node.clone()));
            }

            let found_left = recurse(node.borrow().left.as_ref(), p, q);

            match found_left {
                found_left @ Some((Found::Both, _)) => return found_left,
                found_left @ Some((Found::P, _)) => found_p = found_left,
                found_left @ Some((Found::Q, _)) => found_q = found_left,
                _ => ()
            }

            let found_right = recurse(node.borrow().right.as_ref(), p, q);

            match found_right {
                found_right @ Some((Found::Both, _)) => return found_right,
                found_right @ Some((Found::P, _)) => found_p = found_right,
                found_right @ Some((Found::Q, _)) => found_q = found_right,
                _ => ()
            }

            match (found_p.is_some(), found_q.is_some()) {
                (true, true) => Some((Found::Both, node.clone())),
                (true, false) => found_p,
                (false, true) => found_q,
                _ => None
            }
        }

        match recurse(root.as_ref(), p, q) {
            Some((Found::Both, result)) => Some(result),
            _ => None
        }
    }
}