前端进阶之旅前端进阶之旅
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
  • React专栏

    • React组合式开发实战

      • 前端开发的四个时代
      • 企业管理系统的前世今生
      • 可视化页面搭建工具
      • 实战篇 01:开发前准备
      • 实战篇 02:项目脚手架
      • 实战篇 03:页面布局方案
      • 实战篇 04:权限管理机制
      • 实战篇 05:菜单匹配逻辑
      • 实战篇 06:消息通知设计
      • 实战篇 07:多语言支持
      • 继往开来:可视化页面搭建工具
    • React Hooks与Immutable实战

    • React SSR服务端渲染与同构实践

    • IM聊天系统前端开发实践

    • 微前端开发实战

    • React进阶实践

  • Vue专栏

  • 移动端专栏

  • Node专栏

  • 前端工程化专栏

  • 算法专栏

  • Typescript专栏

  • 其他专栏

完整面试题地址:
作者:程序员poetry
扫码关注作者公众号:「前端进阶之旅」 每天分享技术干货
前端进阶之旅公众号二维码

# 二叉树中和为某一值的路径

输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

# 思路

套用回溯算法的思路

设定一个结果数组result来存储所有符合条件的路径

设定一个栈stack来存储当前路径中的节点

设定一个和sum来标识当前路径之和

  • 从根结点开始深度优先遍历,每经过一个节点,将节点入栈

  • 到达叶子节点,且当前路径之和等于给定目标值,则找到一个可行的解决方案,将其加入结果数组

  • 遍历到二叉树的某个节点时有2个可能的选项,选择前往左子树或右子树

  • 若存在左子树,继续向左子树递归

  • 若存在右子树,继续向右子树递归

  • 若上述条件均不满足,或已经遍历过,将当前节点出栈,向上回溯

# 代码

    function FindPath(root, expectNumber) {
      const result = [];
      if (root) {
        FindPathCore(root, expectNumber, [], 0, result);
      }
      return result;
    }

    function FindPathCore(node, expectNumber, stack, sum, result) {
      stack.push(node.val);
      sum += node.val;
      if (!node.left && !node.right && sum === expectNumber) {
        result.push(stack.slice(0));
      }
      if (node.left) {
        FindPathCore(node.left, expectNumber, stack, sum, result);
      }
      if (node.right) {
        FindPathCore(node.right, expectNumber, stack, sum, result);
      }
      stack.pop();
    }
@前端进阶之旅: 代码已经复制到剪贴板

# 考察点

  • 二叉树
  • 回溯算法
fe
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
  • React专栏

    • React组合式开发实战

      • 前端开发的四个时代
      • 企业管理系统的前世今生
      • 可视化页面搭建工具
      • 实战篇 01:开发前准备
      • 实战篇 02:项目脚手架
      • 实战篇 03:页面布局方案
      • 实战篇 04:权限管理机制
      • 实战篇 05:菜单匹配逻辑
      • 实战篇 06:消息通知设计
      • 实战篇 07:多语言支持
      • 继往开来:可视化页面搭建工具
    • React Hooks与Immutable实战

    • React SSR服务端渲染与同构实践

    • IM聊天系统前端开发实践

    • 微前端开发实战

    • React进阶实践

  • Vue专栏

  • 移动端专栏

  • Node专栏

  • 前端工程化专栏

  • 算法专栏

  • Typescript专栏

  • 其他专栏