leetcode 257. Binary Tree Paths-白红宇

leetcode 257. Binary Tree Paths

阅读量：2380 次

发布时间：2019-05-10

本文共 3733 字，大约阅读时间需要 12 分钟。

/*leetcode 257. Binary Tree PathsGiven a binary tree, return all root-to-leaf paths.For example, given the following binary tree:  1/   \2    3\ 5All root-to-leaf paths are:["1->2->5", "1->3"]题目大意：求解二叉树中所有根节点到叶子节点的路径解题思路：*/#include "TreeInclude.h"#include 
   
    #include 
    
     class Solution{public:    //iterator    vector
     
       binaryTreePaths(TreeNode* root)    {        vector
      
        ret;        if (!root)            return ret;        //存放路径的栈        stack
       
         stk;        stk.push(root);        //存放路径的数        vector
        
          pathVal({root->val}); //是否已经遍历过了 unordered_set
         
           umap; umap.insert(root); TreeNode* cur; while (stk.size()) { cur = stk.top(); //如果左右子树都为空则： //找到一条路径，压入返回数组中；继续回溯 if (!cur->left && !cur->right) { ret.push_back(GenHelper(pathVal)); pathVal.pop_back(); stk.pop(); } else { if (cur->left) { auto isLeft = umap.find(cur->left); if (isLeft == umap.end())//没有访问过 { //开始访问：把值存放在值得数组中，把节点放到栈中，并标记为已访问 pathVal.push_back(cur->left->val); stk.push(cur->left); umap.insert(cur->left); continue; } } //能够到这里：说明左子树为空或者左子树已经访问过了 //因为我们要每次访问一条路径，因此不能把两条路径混杂了。 if (cur->right) { auto isRight = umap.find(cur->right); if (isRight == umap.end())//没有访问过 { //开始访问：把值存放在值得数组中，把节点放到栈中，并标记为已访问 pathVal.push_back(cur->right->val); stk.push(cur->right); umap.insert(cur->right); continue; } } //左右子树都访问完了 pathVal.pop_back(); stk.pop(); } } return ret; } string GenHelper(vector
          
            v) { int len = v.size(); string ret; if (len == 0) return ret; ret += to_string(v[0]); for (int i = 1; i < len; ++i) ret += ("->" + to_string(v[i])); return ret; }};class Solution1{public: //recusive vector
           
             binaryTreePaths(TreeNode* root) { vector
            
              ret; if (!root) return ret; FindHelp(ret, root, to_string(root->val)); return ret; } void FindHelp(vector
             
              & ret, TreeNode* root, string str) { //退出条件：左右子树都为空 if (!root->left && !root->right) { ret.push_back(str); return; } if (root->left) { FindHelp(ret, root->left, str + "->" + to_string(root->left->val)); } if (root->right) { FindHelp(ret, root->right, str + "->" + to_string(root->right->val)); } }};void TEST(){ Solution sol; vector
              
                v{ 1,2,3,-1,5 }; TreeNode* root = CreateTree(v); vector
               
                 ret = sol.binaryTreePaths(root); for (auto str : ret) cout << str << endl;}int main(){ TEST(); return 0;}

头文件

#ifndef _TREE_INCLUDE_H_ #define _TREE_INCLUDE_H_#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;// 节点数据结构struct TreeNode{    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};//使用数组创建二叉树void CreateNode(const vector
       
        & v, TreeNode* cur, int curIndex){    int len = v.size();    if (len == 0 || cur == NULL || curIndex < 0 || curIndex >= len)        return;    if ((2 * curIndex + 1 < len) && (v[2*curIndex+1] != -1))    {        TreeNode* tmp = new TreeNode(v[2 * curIndex + 1]);        cur->left = tmp;    }    else        cur->left = NULL;    if ((2 * curIndex + 2 < len) && (v[2*curIndex+2] != -1))    {        TreeNode* tmp = new TreeNode(v[2 * curIndex + 2]);        cur->right = tmp;    }    else        cur->right = NULL;    CreateNode(v, cur->left, 2 * curIndex + 1);    CreateNode(v, cur->right, 2 * curIndex + 2);}TreeNode* CreateTree(const vector
        
         & v){ int len = v.size(); if (len == 0) return NULL; TreeNode* root = new TreeNode(v[0]); CreateNode(v, root, 0); return root;}void FirstOrderTraverse(TreeNode* root){ if (root == NULL) return; cout << root->val << " "; FirstOrderTraverse(root->left); FirstOrderTraverse(root->right); //cout << endl;}void MakeEmpty(TreeNode* root){ if (root != NULL) { MakeEmpty(root->left); MakeEmpty(root->right); delete root; }}#endif //