Question
Formatted question description: https://leetcode.ca/all/257.html
257 Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
["1->2->5", "1->3"]
@tag-tree
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
Java
-
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); } } } }
-
// 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, 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