实现二叉树所有路径

问题

实现 treePath 方法，返回二叉树从根节点到所有叶子节点的路径，路径格式为 "1->2->5"。

const tree: Tree = {
  value: 1,
  left: {
    value: 2,
    right: { value: 5 }
  },
  right: { value: 3 }
};

treePath(tree); // [ '1->2->5', '1->3' ]

解答

使用深度优先遍历（DFS），递归遍历每个节点，记录路径，到达叶子节点时保存完整路径。

type Tree = {
  value: number;
  left?: Tree;
  right?: Tree;
};

function treePath(root: Tree): string[] {
  const result: string[] = [];
  
  function dfs(node: Tree, path: string) {
    // 构建当前路径
    const currentPath = path ? `${path}->${node.value}` : `${node.value}`;
    
    // 叶子节点：没有左右子树
    if (!node.left && !node.right) {
      result.push(currentPath);
      return;
    }
    
    // 递归遍历左子树
    if (node.left) {
      dfs(node.left, currentPath);
    }
    
    // 递归遍历右子树
    if (node.right) {
      dfs(node.right, currentPath);
    }
  }
  
  dfs(root, '');
  return result;
}

关键点

• 使用递归实现深度优先遍历
• 判断叶子节点的条件是左右子树都不存在
• 路径字符串在递归过程中逐步拼接
• 只在到达叶子节点时才将路径加入结果数组