Lintcode: 두 갈래 트리의 모든 경로

2699 단어 Lintcode

질문:


두 갈래 나무를 주어 뿌리 노드에서 잎 노드까지의 모든 경로를 찾아라.

예:


예제 1:
 :{1,2,3,#,5}
 :["1->2->5","1->3"]
 :
   1
 /   \
2     3
 \
  5

예제 2:
 :{1,2}
 :["1->2"]
 :
   1
 /   
2     

python:
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of the binary tree
    @return: all root-to-leaf paths
    """
    def findLastNode(self, root, path, result):
        if root == None:
            return None
        path += str(root.val)
        if root.left == None and root.right == None:
            result.append(path)
        else:
            path += "->"
            if root.left != None:
                self.findLastNode(root.left, path, result)
            if root.right != None:
                self.findLastNode(root.right, path, result)
                
    def binaryTreePaths(self, root):
        # write your code here
        if root == None:
            return []
        path = ""
        result = []
        self.findLastNode(root, path, result)
        return result

C++:
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the root of the binary tree
     * @return: all root-to-leaf paths
     */
    void findLastNode(TreeNode *root, string path, vector &result)
    {
        if(root == NULL)
        {
            return;
        }
        path += to_string(root->val);
        if(root->left == NULL && root->right == NULL)
        {
            result.push_back(path);
        }else{
            path += "->";
            if(root->left != NULL)
            {
                findLastNode(root->left, path, result);
            }
            if(root->right != NULL)
            {
                findLastNode(root->right, path, result);
            }
        }
    }
    vector binaryTreePaths(TreeNode * root) {
        // write your code here
        if(root == NULL)
        {
            return vector();
        }
        string path = "";
        vector result;
        findLastNode(root, path, result);
        return result;
    }
};

좋은 웹페이지 즐겨찾기