首页 > itarticle > algorithm notes: leetcode#257 binary tree paths

algorithm notes: leetcode#257 binary tree paths

admin 11月 12, 2020 0

Problem

Solution

Initial thoughts

Python implementation

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class :
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        ans = []
        def dfs(node, string):
            if node is None:
                return node
            result = string+"->"+str(node.val) if string else str(node.val)
            if node.left is None and node.right is None:
                ans.append(result)
            else:
                dfs(node.left, result)
                dfs(node.right, result)
                
        dfs(root, "")
        return ans

Java implementation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class  {
    private List<String> ans = new ArrayList<>();
    
    private void dfs(TreeNode node, String str){
        if(node == null){ return ; }
        String result = str.equals("") ? Integer.toString(node.val) : str+"->"+Integer.toString(node.val);
        if(node.left==null && node.right==null){ 
            ans.add(result); }else{
            dfs(node.left, result);
            dfs(node.right, result);
        }
    }
    
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root, "");
        return ans;
    }
}

Time complexity

O(n)

Space complexity

O(n)

Links

257. Binary Tree Paths
(中文版) 算法笔记: 力扣#257 二叉树的所有路径