网站建设与管理教程视频教程,成品网站 修改首页,个人简历 网站开发,crm软件免费Problem: 257. 二叉树的所有路径 文章目录 题目描述思路复杂度Code 题目描述 思路
遍历思想(利用二叉树的先序遍历) 利用先序遍历的思想#xff0c;我门用一个List变量path记录当前先序遍历的节点#xff0c;当遍历到根节点时#xff0c;将其添加到另一个List变量res中我门用一个List变量path记录当前先序遍历的节点当遍历到根节点时将其添加到另一个List变量res中当递归往回归的时候删除当前path中的最后一个值 复杂度
时间复杂度: O ( n ) O(n) O(n);其中 n n n为二叉树的节点个数 空间复杂度: O ( h ) O(h) O(h)其中 h 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 ListString binaryTreePaths(TreeNode root) {traverse(root);return res;}// Record the traverse recursive pathLinkedListString path new LinkedList();// Records all paths from the root to the leaf nodeLinkedListString 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();}
}
