個人主頁：元清加油_【C++】,【C語言】,【數(shù)據(jù)結(jié)構(gòu)與算法】-CSDN博客

個人專欄

力扣遞歸算法題 ? ? ? 【 ? ? 】
【C++】 ? ? ? ? ? ? ? ? ?【 ? 】
數(shù)據(jù)結(jié)構(gòu)與算法 ? ? ? 【 ? ?】

前言：這個專欄主要講述遞歸遞歸、搜索與回溯算法，所以下面題目主要也是這些算法做的 ?

我講述題目會把講解部分分為3個部分：
1、題目解析

2、算法原理思路講解

3、代碼實現(xiàn)

二叉樹的所有路徑

題目鏈接：二叉樹的所有路徑

題目

給你一個二叉樹的根節(jié)點?root?，按?任意順序?，返回所有從根節(jié)點到葉子節(jié)點的路徑。

葉子節(jié)點?是指沒有子節(jié)點的節(jié)點。

示例 1：

文章來源地址http://www.zghlxwxcb.cn/news/detail-804942.html

輸入：root = [1,2,3,null,5]
輸出：["1->2->5","1->3"]

示例 2：

輸入：root = [1]
輸出：["1"]

提示：

• 樹中節(jié)點的數(shù)目在范圍?[1, 100]?內(nèi)
• -100 <= Node.val <= 10

解法

題目解析

題目意思很簡單，給我們一顆二叉樹，讓我們返回二叉樹所有的路徑

例如：

輸入：root = [1,2,3,null,5]
輸出：["1->2->5","1->3"]

算法原理思路講解???

1. 如果當(dāng)前節(jié)點不為空，就將當(dāng)前節(jié)點的值加?路徑 path 中，否則直接返回；
2. 判斷當(dāng)前節(jié)點是否為葉?節(jié)點，如果是，則將當(dāng)前路徑加?到所有路徑的存儲數(shù)組 ret?中；
3. 否則，將當(dāng)前節(jié)點值加上 "->" 作為路徑的分隔符，繼續(xù)遞歸遍歷當(dāng)前節(jié)點的左右?節(jié)點。

?代碼實現(xiàn)?

• 時間復(fù)雜度：O(N^2)，其中 N 表示節(jié)點數(shù)目。在深度優(yōu)先搜索中每個節(jié)點會被訪問一次且只會被訪問一次，每一次會對 path 變量進行拷貝構(gòu)造，時間代價為 O(N)，故時間復(fù)雜度為 O(N^2)。
• 空間復(fù)雜度：O(N^2)，其中 N 表示節(jié)點數(shù)目。除答案數(shù)組外我們需要考慮遞歸調(diào)用的棧空間。在最壞情況下，當(dāng)二叉樹中每個節(jié)點只有一個孩子節(jié)點時，即整棵二叉樹呈一個鏈狀，此時遞歸的層數(shù)為 NNN.

  /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
   *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
   * };
   */
  class Solution 
  {
  public:
      vector<string> ret;
  
      void dfs(TreeNode* root , string path)
      {
          if (root != nullptr)
              path += to_string(root->val);
          else
              return ;
          
          if(root->left == nullptr && root->right == nullptr)
          {
              ret.push_back(path);
              return;
          }
          path += "->";
          if(root->left) dfs(root->left, path);
          if(root->right) dfs(root->right, path);
      }
  
      vector<string> binaryTreePaths(TreeNode* root) 
      {
          string path;
          if(root == nullptr) 
              return ret;
  
          dfs(root,path);
          return ret;
      }
  };

到了這里，關(guān)于LeetCode刷題--- 二叉樹的所有路徑的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！