257. Binary Tree Paths
Given the root of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.
Example 1:
Input: root = [1,2,3,null,5]
Output: [“1->2->5”,“1->3”]
Example 2:
Input: root = [1]
Output: [“1”]
Constraints:
- The number of nodes in the tree is in the range [1, 100].
- -100 <= Node.val <= 100
From: LeetCode
Link: 257. Binary Tree Paths
Solution:
Ideas:
1. TreeNode Structure: The structure for a binary tree node is defined with integer value, left child, and right child pointers.
2. DFS Helper Function: The dfs function performs a depth-first search to find all paths from the root to the leaves. It constructs the path as a string and adds it to the paths array when a leaf is encountered.
3. Main Function: The binaryTreePaths function initializes the paths array and calls the dfs function to populate it. It also sets the return size of the paths array.
4. Helper Functions:
- newNode creates a new tree node.
- freeTree frees the allocated tree nodes.
- freePaths frees the allocated paths array.
Code:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
void dfs(struct TreeNode* root, char* path, int length, char** paths, int* size) {if (root == NULL) return;int len = snprintf(path + length, 100 - length, "%d", root->val);length += len;if (root->left == NULL && root->right == NULL) {paths[*size] = (char*)malloc((length + 1) * sizeof(char));strcpy(paths[*size], path);(*size)++;} else {length += snprintf(path + length, 100 - length, "->");dfs(root->left, path, length, paths, size);dfs(root->right, path, length, paths, size);}
}char** binaryTreePaths(struct TreeNode* root, int* returnSize) {char** paths = (char**)malloc(100 * sizeof(char*));char path[100];*returnSize = 0;if (root != NULL) {dfs(root, path, 0, paths, returnSize);}return paths;
}// Helper function to create a new tree node
struct TreeNode* newNode(int data) {struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = data;node->left = NULL;node->right = NULL;return node;
}// Helper function to free the allocated tree nodes
void freeTree(struct TreeNode* root) {if (root == NULL) return;freeTree(root->left);freeTree(root->right);free(root);
}// Helper function to free the paths array
void freePaths(char** paths, int size) {for (int i = 0; i < size; i++) {free(paths[i]);}free(paths);
}