1. // const _ = require('lodash');
    3. // function sayHello() {
    4. //   console.log('Hello, World');
    5. // }
    7. // _.times(5, sayHello);
    10. // 有一棵二叉树，二叉树中有两个节点s和t，输出从s到t的最短有向路径。其中，‘U’代表向上，‘L’代表向左，‘R’代表向右
    11. // Example：
    12. //      1
    13. //     / \
    14. //    2   3
    15. //   /   / \
    16. //  4   5   6
    18. // s = 4, t = 5, output: "UU    RL" (4->2->1->3->5)
    19. // s = 4, t = 6,  U  R
    21. function test(root, s, t) {
    22.   let result = [];
    24.   // 面试官问递归的返回是什么，怎么考虑
    25.   function walk(node, path) {
    26.     if (node === null || node === undefined) {
    27.       return;
    28.     }
    30.     if (node.val === s.val || node.val === t.val) {
    31.       result.push(path);
    32.       return true;
    33.     }
    35.     let r1= walk(node.left, [...path, 'L']);
    36.     let r2 = walk(node.right, [...path, 'R']);
    38.     if (r1 && r2) {
    39.       let n = path.length; // 减去公共的首部
    40.       result[0] = result.slice(n);
    41.       result[1] = result.slice(n);
    42.     }
    44.   }
    46.   walk(root, []);
    48.   console.log(result);
    50.   if (result.length === 2) {
    51.     let tmp = result[0].map(() => 'U');
    52.     return [...tmp, ...result[1]].join('');
    53.   }
    55.   if (result.length === 1) {
    56.     let tmp = result[0].map(() => 'U');
    57.     return tmp.join('');
    58.   }
    60.   return result;
    61. }
    63. function Node(val, left, right) {
    64.   this.val = val;
    65.   this.left = left;
    66.   this.right = right;
    67. }
    69. //      1
    70. //     / \
    71. //    2   3
    72. //   /   / \
    73. //  4   5   6
    74. const n1 = new Node(1);
    75. const n2 = new Node(2);
    76. const n3 = new Node(3);
    77. const n4 = new Node(4);
    78. const n5 = new Node(5);
    79. const n6 = new Node(6);
    81. n1.left = n2;
    82. n1.right = n3;
    83. n2.left = n4;
    84. n3.left = n5;
    85. n3.right = n6;
    88. // console.log(test(n1, n4, n2));
    90. console.log(test(n1, n5, n6));