資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在 C++ 中查詢給定二叉樹的左葉節點之和
假設我們有一個二叉樹，它有一個根節點，以及它的左子節點和右子節點。任務是找到樹中所有左葉節點的總和。
例如
輸入-1
輸出
15
解釋：在給定的輸入二叉樹中，所有左葉節點的和是 9 + 4 + 2 = 15。所以，輸出是 15。
解決這個問題的方法
我們有一個二叉樹，任務是找到所有位於其父節點左側的葉節點的和。
解決這個問題的遞迴方法是檢查根節點的左節點是否為空。如果為空，則計算其左節點的和，併為右節點找到遞迴和。因此，對於每個節點，我們將遞迴地檢查並找到其和。
- 將具有根節點及其左子節點和右子節點的二叉樹作為輸入。
- 一個整數函式 `leftLeafSum(treenode*root)` 將根節點作為輸入，並返回所有位於其父節點左側的葉節點的和。
- 如果根節點為空或為 NULL，則返回“零”，否則檢查根節點的左節點。
- 如果根節點的左節點沒有子節點，則遞迴地檢查右節點。
- 遞迴地返回左子節點和右子節點的和。
示例
#include<bits/stdc++.h>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
int leftLeafSum(treenode * root) {
if (root == NULL) {
return 0;
}
if (root -> left and!root -> left -> left and!root -> left -> right) {
return root -> left -> data + leftLeafSum(root -> right);
}
return leftLeafSum(root -> left) + leftLeafSum(root -> right);
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root -> left = createNode(2);
root -> right = createNode(2);
root -> left -> right = createNode(7);
root -> left -> left = createNode(5);
root -> right -> left = createNode(5);
root -> right -> right = createNode(7);
int sum = leftLeafSum(root);
cout << sum << endl;
return 0;
}執行以上程式碼將生成以下輸出：
輸出
10
解釋：左側的葉節點是 5 和 5，它們位於其父節點的左側，因此所有葉節點的和 = 10。
更新於：2021年2月23日
950 次檢視
廣告