leetcode/257-binary-tree-paths.cpp at master · duxins/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//  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"]
//
//  Tags: Tree, Depth-first Search
//
//  https://leetcode.com/problems/binary-tree-paths/

#include <iostream>
#include <gtest/gtest.h>
#include <tree/tree.h>

using namespace std;

class Solution {
private:
    void dfs(TreeNode *root, string path, vector<string> &result){
        if(root == NULL) return;

        if(root->left == NULL && root->right == NULL){
            result.push_back(path);
        }

        if(root->left){
            dfs(root->left, path + "->" + to_string(root->left->val), result);
        }

        if(root->right){
            dfs(root->right, path + "->" + to_string(root->right->val), result);
        }

    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        if(root == NULL) {
            return result;
        }
        dfs(root, to_string(root->val), result);
        return result;
    }
};

TEST(leetcode_257_binary_tree_paths, Basic)
{
    Solution *solution = new Solution();
    TreeNode *root = tree_init({"1", "2", "3", "#", "5"});
    vector<string> expected = {"1->2->5", "1->3"};
    EXPECT_EQ(expected, solution->binaryTreePaths(root));

    root = tree_init({"-64","12","18","-4","-53","#","76","#","-51","#","#","-93","3","#","-31","47","#","3","53","-81","33","4","#","-51","-44","-60","11","#","#","#","#","78","#","-35","-64","26","-81","-31","27","60","74","#","#","8","-38","47","12","-24","#","-59","-49","-11","-51","67","#","#","#","#","#","#","#","-67","#","-37","-19","10","-55","72","#","#","#","-70","17","-4","#","#","#","#","#","#","#","3","80","44","-88","-91","#","48","-90","-30","#","#","90","-34","37","#","#","73","-38","-31","-85","-31","-96","#","#","-18","67","34","72","#","-17","-77","#","56","-65","-88","-53","#","#","#","-33","86","#","81","-42","#","#","98","-40","70","-26","24","#","#","#","#","92","72","-27","#","#","#","#","#","#","-67","#","#","#","#","#","#","#","-54","-66","-36","#","-72","#","#","43","#","#","#","-92","-1","-98","#","#","#","#","#","#","#","39","-84","#","#","#","#","#","#","#","#","#","#","#","#","#","-93","#","#","#","98"});
    expected = {"-64->12->-4->-51->-31->-81","-64->12->-4->-51->-31->33","-64->12->-53","-64->18->76->-93->47->4->78","-64->18->76->3->3->-51->-35->8","-64->18->76->3->3->-51->-35->-38->-67","-64->18->76->3->3->-51->-64->47->-37->3->73->-33","-64->18->76->3->3->-51->-64->47->-37->3->-38->86->-54","-64->18->76->3->3->-51->-64->47->-37->3->-38->86->-66","-64->18->76->3->3->-51->-64->47->-37->80->-31->81->-36","-64->18->76->3->3->-51->-64->47->-37->80->-31->-42->-72","-64->18->76->3->3->-51->-64->47->-37->80->-85","-64->18->76->3->3->-51->-64->47->-19->44->-31->98->43","-64->18->76->3->3->-51->-64->47->-19->44->-31->-40","-64->18->76->3->3->-51->-64->47->-19->44->-96->70->-92","-64->18->76->3->3->-51->-64->47->-19->44->-96->-26->-1->-93","-64->18->76->3->3->-51->-64->47->-19->44->-96->-26->-98","-64->18->76->3->3->-51->-64->47->-19->-88","-64->18->76->3->3->-51->-64->12->10->-91->-18->24","-64->18->76->3->3->-51->-64->12->10->-91->67","-64->18->76->3->3->-51->-64->12->-55->48->34->92","-64->18->76->3->3->-51->-64->12->-55->48->72->72","-64->18->76->3->3->-51->-64->12->-55->48->72->-27->39->98","-64->18->76->3->3->-51->-64->12->-55->-90->-17","-64->18->76->3->3->-44->26->-24->72->-30->-77","-64->18->76->3->3->-44->-81->-59","-64->18->76->3->3->-44->-81->-49->-70->90->56","-64->18->76->3->3->-44->-81->-49->-70->90->-65->-67->-84","-64->18->76->3->3->-44->-81->-49->17->-34->-88","-64->18->76->3->3->-44->-81->-49->17->-34->-53","-64->18->76->3->3->-44->-81->-49->17->37","-64->18->76->3->53->-60->-31->-11->-4","-64->18->76->3->53->-60->-31->-51","-64->18->76->3->53->-60->27->67","-64->18->76->3->53->11->60","-64->18->76->3->53->11->74"};
    EXPECT_EQ(expected, solution->binaryTreePaths(root));

    root = tree_init({"37","-34","-48","#","-100","-100","48","#","#","#","#","-54","#","-71","-22","#","#","#","8"});
    expected = {"37->-34->-100","37->-48->-100","37->-48->48->-54->-71","37->-48->48->-54->-22->8"};
    EXPECT_EQ(expected, solution->binaryTreePaths(root));

    root = NULL;
    expected = {};
    EXPECT_EQ(expected, solution->binaryTreePaths(root));
}

int main(int argc, char *argv[]) {
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}