用 C++ 找到二叉樹左側檢視的程式

假設我們有一棵二叉樹，如果從左側看這棵樹，那麼我們可以看到它的某些元素。我們必須顯示這些元素。因此，如果這棵樹是這樣的 −

輸出將為 [1,2,5]

為了解決這個問題，我們將遵循以下步驟 −

  • 定義一個數組 ret

  • 定義一個函式 dfs()，它會使節點 c 初始化為 1，

  • 如果節點為空，那麼 −

    • 返回

  • 如果 c > lvl，那麼 −

    • lvl := c

    • 將節點的值插入 ret

  • dfs(該節點的左側，c + 1)

  • dfs(該節點的右側，c + 1)

  • 在 main 方法中，執行以下操作 −

  • lvl := -1

  • dfs(根，0)

  • 返回 ret


讓我們看看以下實現以獲得更好的理解 −

例項

 即時演示

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = right = NULL;
   }
};
class Solution {
   public:
   vector <int> ret;
   int lvl;
   void dfs(TreeNode* node, int c = 1){
      if(!node)
         return;
      if(c > lvl){
         lvl = c;
         ret.push_back(node->val);
      }
      dfs(node->left, c + 1);
      dfs(node->right, c + 1);
   }
   vector<int> solve(TreeNode* root) {
      lvl = -1;
      dfs(root, 0);
      return ret;
   }
};
main(){
   TreeNode *root = new TreeNode(1);
   root->left = new TreeNode(2);
   root->right = new TreeNode(3);
   root->left->right = new TreeNode(5);
   root->right->right = new TreeNode(4);
   Solution ob;
   print_vector(ob.solve(root));
}

輸入

TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(4);

輸出

[1,2,5]

更新於：2020-10-10

74 次瀏覽

啟動你的 職業生涯

完成課程獲取認證

開始
廣告