Leetcode 257. Binary Tree Paths(python+cpp)

题目

Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.

解法 1：DFS

参考129解法的前半部分

class Solution:def binaryTreePaths(self, root: TreeNode) -> List[str]:def create_path(root,curr_path):if not root.right and not root.left:if not curr_path:pathlist.append(str(root.val))else:pathlist.append(curr_path+'->'+str(root.val))if root.left:if not curr_path:create_path(root.left,str(root.val))else:create_path(root.left,curr_path+'->'+str(root.val))if root.right:if not curr_path:create_path(root.right,str(root.val))else:create_path(root.right,curr_path+'->'+str(root.val))if not root:return []pathlist = []create_path(root,'')return pathlist

时间复杂度：O(N)
空间复杂度：O(N)

解法2：改进版DFS

class Solution:def binaryTreePaths(self, root: TreeNode) -> List[str]:def create_path(root,curr_path):if root:curr_path += str(root.val)if not root.left and not root.right:pathlist.append(curr_path)else:curr_path += '->'create_path(root.left,curr_path)create_path(root.right,curr_path)pathlist = []create_path(root,'')return pathlist

时间复杂度：O(N)，这种改进版本虽然代码简单了很多，时间复杂度看起来也一样，但是提交结果却比解法1差很多，我也不太知道是为什么，欢迎小伙伴评论发表看法
空间复杂度：O(N)

二刷改进

这次的recursion思路更清晰，代码如下：

class Solution:def binaryTreePaths(self, root: TreeNode) -> List[str]:def append_path(root,path):if not root.left and not root.right:ans.append(path)returnif root.left:append_path(root.left,path+'->'+str(root.left.val))if root.right:append_path(root.right,path+'->'+str(root.right.val))if not root:return []ans = []append_path(root,str(root.val))return ans

同时也可以用backtracking来做，backtracking的话先把所有节点都放到一个列表里，在形成结果是加入箭头即可，代码如下：

class Solution:def binaryTreePaths(self, root: TreeNode) -> List[str]:def append_path(root,path):if not root.left and not root.right:curr = ''for ele in path:if curr:curr += '->'curr += str(ele)ans.append(curr)if root.left:path.append(root.left.val)append_path(root.left,path)path.pop()if root.right:path.append(root.right.val)append_path(root.right,path)path.pop()if not root:return []ans = []append_path(root,[root.val])return ans

然后用iteration来实现，就是用一个stack，因为recursion的本质就是stack，所以实际上是一模一样的

class Solution:def binaryTreePaths(self, root: TreeNode) -> List[str]:if not root:return []ans = []stack = [(root,str(root.val))]while stack:node,path = stack.pop()if not node.left and not node.right:ans.append(path)if node.left:stack.append((node.left,path+'->'+str(node.left.val)))if node.right:stack.append((node.right,path+'->'+str(node.right.val)))return ans

CPP解法

class Solution {
    
public:vector<string> pathlist;void create_path(TreeNode* root, string curr_path){
    if(root != NULL){
    curr_path = curr_path + to_string(root->val);if(root->left==NULL && root->right==NULL)pathlist.push_back(curr_path);elsecurr_path = curr_path + "->";create_path(root->left,curr_path);create_path(root->right,curr_path);}}vector<string> binaryTreePaths(TreeNode* root) {
    string s = "";create_path(root,s);return pathlist;   }
};

时间复杂度：O(N)
空间复杂度：O(N)