LeetCode Notes: Binary Tree Paths

#leetcode

Question

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

Solution

Analysis:

Depth first search, use recursion to traverse all left and right child nodes, when there are no child nodes, store the path.

Code:

/**
  * Definition for a binary tree node.
  * function TreeNode(val, left, right) {
  * this.val = (val===undefined? 0: val)
  * this.left = (left===undefined? null: left)
  * this.right = (right===undefined? null: right)
  *}
  */
/**
  * @param {TreeNode} root
  * @return {string[]}
  */
var binaryTreePaths = function(root) {
     let paths = [];
     const findPath = (node,path) => {

         // make sure node has a value
         if(!node) return
        
         // store new node value
         path += node.val

         // If there is no child node, directly store the path of the current leaf node
         if(node.left == null && node.right == null){
             paths.push(path)
         }else{
             // There are child nodes, continue the depth-first search
             path +='->'
             findPath(node.left,path);
             findPath(node.right,path)
         }
     }
     findPath(root,'')
     return paths
};

Reference

Comments