Problem: 257. 二叉树的所有路径

题目描述

思路

遍历思想(利用二叉树的先序遍历)

利用先序遍历的思想，我门用一个List变量path记录当前先序遍历的节点，当遍历到根节点时，将其添加到另一个List变量res中，当递归往回归的时候删除当前path中的最后一个值

复杂度

时间复杂度:

$O(n)$;其中$n$为二叉树的节点个数

空间复杂度:

$O(h)$；其中$h$为二叉树的高度

Code

/*
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<String> binaryTreePaths(TreeNode root) {traverse(root);return res;}// Record the traverse recursive pathLinkedList<String> path = new LinkedList<>();// Records all paths from the root to the leaf nodeLinkedList<String> res = new LinkedList<>();private void traverse(TreeNode root) {if (root == null) {return;}// leaf rootif (root.left == null && root.right == null) {path.addLast(root.val + "");// Add this path to resres.addLast(String.join("->", path));path.removeLast();return;}// Preorder traversal positionpath.addLast(root.val + "");// Recursively traverse the left and right subtreestraverse(root.left);traverse(root.right);// Post order traversal positionpath.removeLast();}
}