In this Leetcode Binary Tree Paths problem solution we have given the root of a binary tree, return all root-to-leaf paths in any order. A leaf is a node with no children.
Problem solution in Python.
class Solution: def binaryTreePaths(self, root: TreeNode) -> List[str]: if root is None: return [] path = str(root.val) res = [] self.traverse(root,path,res) return res def traverse(self, root, path, res): if root.left is None and root.right is None: res.append(path) if root.left is not None: self.traverse(root.left, path+"->"+str(root.left.val), res) if root.right is not None: self.traverse(root.right, path+"->"+str(root.right.val), res)
Problem solution in Java.
public class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> list = new ArrayList<String>(); if(root == null) return list; StringBuilder str = new StringBuilder(); binaryHelper(root,list,str); return list; } private void binaryHelper(TreeNode root, List<String> list, StringBuilder str){ if(root == null) return; StringBuilder newStr = new StringBuilder(str); if(newStr.length() != 0) newStr.append("->"); newStr.append(root.val); if(root.left == null && root.right == null) { list.add(newStr.toString()); return; } binaryHelper(root.left,list,newStr); binaryHelper(root.right,list,newStr); } }
Problem solution in C++.
vector<string> binaryTreePaths(TreeNode* root) { if(root==NULL) return {}; else { vector<string> lefty= binaryTreePaths(root->left); vector<string> righty= binaryTreePaths(root->right); vector<string> ans; string rooty=to_string(root->val); int l=lefty.size(), r=righty.size(); if(l==0 and r==0) { vector<string> v; v.push_back(rooty); return v; } for(int i=0;i<l;i++) { string s=rooty+"->"+lefty[i]; ans.push_back(s); } for(int i=0;i<r;i++) { string s=rooty+"->"+righty[i]; ans.push_back(s); } return ans; } }
Problem solution in C.
#define MAX_SIZE 1000 void pre_order_str(struct TreeNode *root, char ***res, int *res_size, char str[]) { if(NULL == root) return; char buf[MAX_SIZE]; int append_size = 0; snprintf(buf, MAX_SIZE, "%d", root->val); append_size = strlen(buf); if(strnlen(str, MAX_SIZE) >= 1) { strncat(str, "->", MAX_SIZE); append_size += 2; } strncat(str, buf,MAX_SIZE); pre_order_str(root->left, res, res_size, str); pre_order_str(root->right, res, res_size, str); /*If leaf */ if((!root->left) && (!root->right)) { (*res_size)++; (*res) = realloc((*res), sizeof(char *) * (*res_size)); int size = (*res_size) - 1; (*res)[size] = malloc(sizeof(char) * MAX_SIZE); strncpy((*res)[size], str, MAX_SIZE); } /* when done with node remove ->val from str */ str[strnlen(str, MAX_SIZE) - append_size] = '\0'; } char** binaryTreePaths(struct TreeNode* root, int* returnSize) { char **result = malloc(sizeof(char *) * 1); if(NULL == result) { *returnSize = 0; return NULL; } char str[MAX_SIZE]; str[0] = '\0'; pre_order_str(root, &result, returnSize, str); return result; }
0 Comments