Binary Tree Paths LeetCode Solution | Easy Approach

Minimum Cost to Merge Stones
Share:

Binary Tree Paths Given the root of a binary tree, return all root-to-leaf paths in any order.

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

Binary Tree Paths Solutions

Time: O(n)
Space: O(h)

C++

class Solution {
 public:
  vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> ans;
    dfs(root, {}, ans);
    return ans;
  }

 private:
  void dfs(TreeNode* root, vector<string>&& path, vector<string>& ans) {
    if (!root)
      return;
    if (!root->left && !root->right) {
      ans.push_back(join(path) + to_string(root->val));
      return;
    }

    path.push_back(to_string(root->val) + "->");
    dfs(root->left, move(path), ans);
    dfs(root->right, move(path), ans);
    path.pop_back();
  }

  string join(const vector<string>& path) {
    string joined;
    for (const string& s : path)
      joined += s;
    return joined;
  }
};

Java

 
class Solution {
  public List<String> binaryTreePaths(TreeNode root) {
    List<String> ans = new ArrayList<>();
    dfs(root, new StringBuilder(), ans);
    return ans;
  }

  private void dfs(TreeNode root, StringBuilder sb, List<String> ans) {
    if (root == null)
      return;
    if (root.left == null && root.right == null) {
      ans.add(sb.append(root.val).toString());
      return;
    }

    final int length = sb.length();
    dfs(root.left, sb.append(root.val).append("->"), ans);
    sb.setLength(length);
    dfs(root.right, sb.append(root.val).append("->"), ans);
    sb.setLength(length);
  }
}

Python

 class Solution:
  def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
    ans = []

    def dfs(root: Optional[TreeNode], path: List[str]) -> None:
      if not root:
        return
      if not root.left and not root.right:
        ans.append(''.join(path) + str(root.val))
        return

      path.append(str(root.val) + '->')
      dfs(root.left, path)
      dfs(root.right, path)
      path.pop()

    dfs(root, [])
    return ans

Watch Tutorial

Checkout more Solutions here

Leave a Comment

Your email address will not be published. Required fields are marked *

x