题目地址(257. 二叉树的所有路径)

https://leetcode-cn.com/problems/binary-tree-paths/

题目描述

  1. 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
  3. 叶子节点 是指没有子节点的节点。
  7. 示例 1：
  9. 输入：root = [1,2,3,null,5]
  10. 输出：["1->2->5","1->3"]
  13. 示例 2：
  15. 输入：root = [1]
  16. 输出：["1"]
  21. 提示：
  23. 树中节点的数目在范围 [1, 100] 内
  24. -100 <= Node.val <= 100

前置知识


公司

  • 暂无

思路

前序遍历 第一次碰到左右子树为空时 就输出结果
递归完，要回溯啊，因为path 不能一直加入节点，它还要删节点，然后才能加入新的节点。回溯和递归是一一对应的，有一个递归，就要有一个回溯

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public List<String> binaryTreePaths(TreeNode root) {
  19.             //结果集
  20.             ArrayList<String> res = new ArrayList<>();
  21.             if (root == null) {
  22.                 return res;
  23.             }
  24.             //保存路径信息的临时结果
  25.             ArrayList<Integer> paths = new ArrayList<>();
  26.             loop(res, paths, root);
  27.             return res;
  28.         }
  30.         public void loop(List<String> res, List<Integer> paths, TreeNode root) {
  31.             //每次进入新的递归中 将当前的root的值添加到路径信息中
  32.             paths.add(root.val);
  33.             //递归的结束条件 左右节点都为空时 就可以将路径输出
  34.             if (root.left == null & root.right == null) {
  35.                 StringBuilder sb = new StringBuilder();
  36.                 //先将除最后一个节点的其他节点输出 因为要加->
  37.                 for (int i = 0; i < paths.size() - 1; i++) {
  38.                     sb.append(paths.get(i)).append("->");
  39.                 }
  40.                 //输出最后一个叶节点
  41.                 sb.append(paths.get(paths.size()-1));
  42.                 //添加到结果集
  43.                 res.add(sb.toString());
  44.                 return;
  45.             }
  46.             //如果左子节点!=null 在递归前判断 如果为空的话就不进行下一轮的递归了
  47.             if (root.left != null) {
  48.                 //递归左子节点
  49.                 loop(res, paths, root.left);
  50.                 //回溯 将左子节点的路径删除 因为执行到最后面已经输出到结果集了
  51.                 paths.remove(paths.size()-1);
  52.             }
  53.             //同上
  54.             if (root.right != null) {
  55.                 loop(res, paths, root.right);
  56.                 paths.remove(paths.size()-1);
  57.             }
  58.         }
  59.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：257. 二叉树的所有路径 - 图1#card=math&code=O%28n%29&id=APHPt)
  • 空间复杂度：257. 二叉树的所有路径 - 图2#card=math&code=O%28n%29&id=P8bPS)