Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/257.html
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
Algorithm
In the recursive function, when a leaf node is encountered, there is no left or right child node, then a complete path has been formed at this time, add the current leaf node and save it in the result, and then backtrack.
Code
-
import java.util.ArrayList; import java.util.List; public class Binary_Tree_Paths { public static void main (String[] args) { Binary_Tree_Paths out = new Binary_Tree_Paths(); Solution s = out.new Solution(); TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.right = new TreeNode(5); System.out.println(s.binaryTreePaths(root)); Solution_iteration si = out.new Solution_iteration(); System.out.println(si.binaryTreePaths(root)); } /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution_iteration { public List<Integer> binaryTreePaths(TreeNode root) { if (root == null) { return null; } Binary_Tree_Preorder_Traversal preOderIteration = new Binary_Tree_Preorder_Traversal(); Binary_Tree_Preorder_Traversal.Solution preOrderSolution = preOderIteration.new Solution(); List<Integer> result = preOrderSolution.preorderTraversal(root); return result; } } /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> result = new ArrayList<String>(); if(root == null) { return result; } helper(new String(), root, result); return result; } public void helper(String current, TreeNode root, List<String> result) { if(root.left == null && root.right == null) { result.add(current + root.val); } if(root.left != null) { helper(current + root.val + "->", root.left, result); } if(root.right != null) { helper(current + root.val + "->", root.right, result); } } } } ############ /** * 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 { private List<String> ans; private List<String> t; public List<String> binaryTreePaths(TreeNode root) { ans = new ArrayList<>(); t = new ArrayList<>(); dfs(root); return ans; } private void dfs(TreeNode root) { if (root == null) { return; } t.add(root.val + ""); if (root.left == null && root.right == null) { ans.add(String.join("->", t)); } dfs(root.left); dfs(root.right); t.remove(t.size() - 1); } }
-
// OJ: https://leetcode.com/problems/binary-tree-paths/ // Time: O(NH) // Space: O(H^2) class Solution { private: vector<string> v; void preorder(TreeNode *root, string path) { path += to_string(root->val); if (!root->left && !root->right) { v.push_back(path); return; } path += "->"; if (root->left) preorder(root->left, path); if (root->right) preorder(root->right, path); } public: vector<string> binaryTreePaths(TreeNode* root) { if (!root) return {}; preorder(root, ""); return v; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def binaryTreePaths(self, root: TreeNode) -> List[str]: def dfs(root): if root is None: return t.append(str(root.val)) if root.left is None and root.right is None: ans.append('->'.join(t)) dfs(root.left) dfs(root.right) t.pop() t = [] ans = [] dfs(root) return ans ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param {TreeNode} root # @return {string[]} def binaryTreePaths(self, root): def helper(root, path, res): if root: path.append(str(root.val)) left = helper(root.left, path, res) right = helper(root.right, path, res) if not left and not right: res.append("->".join(path)) path.pop() return True res = [] helper(root, [], res) return res
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func binaryTreePaths(root *TreeNode) []string { var ans []string var t []string var dfs func(root *TreeNode) dfs = func(root *TreeNode) { if root == nil { return } t = append(t, strconv.Itoa(root.Val)) if root.Left == nil && root.Right == nil { ans = append(ans, strings.Join(t, "->")) } dfs(root.Left) dfs(root.Right) t = t[:len(t)-1] } dfs(root) return ans }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function binaryTreePaths(root: TreeNode | null): string[] { let ans = []; let t = []; function dfs(root) { if (!root) return; t.push(String(root.val)); if (!root.left && !root.right) ans.push(t.join('->')); dfs(root.left); dfs(root.right); t.pop(); } dfs(root); return ans; }