資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式：求二叉樹所有右葉節點之和
假設我們有一個二叉樹，我們需要找到給定二叉樹中所有右葉節點的和。
例如，如果輸入如下：
則輸出將為 17，因為二叉樹中有兩個右葉節點，其值分別為 7 和 10。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 dfs()，它將接收節點和一個布林值 add 作為引數。
如果節點為空，則：
返回
如果節點的左子節點和右子節點都為空，並且 add 為非零值，則：
ret := ret + 節點的值
dfs(節點的左子節點, false)
dfs(節點的右子節點, true)
在主方法中，執行以下操作：
ret := 0
dfs(根節點, true)
返回 ret
讓我們看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
int ret = 0;
void dfs(TreeNode* node, bool add){
if(!node)
return ;
if(!node−>left && !node->right && add){
ret += node−>val;
}
dfs(node−>left, false);
dfs(node−>right, true);
}
int solve(TreeNode* root) {
ret = 0;
dfs(root, true);
return ret;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(3);
root−>left = new TreeNode(9);
root−>right = new TreeNode(10);
root−>left−>left = new TreeNode(15);
root−>left−>right = new TreeNode(7);
cout << (ob.solve(root));
}輸入
TreeNode *root = new TreeNode(3); root−>left = new TreeNode(9); root−>right = new TreeNode(10); root−>left−>left = new TreeNode(15); root−>left−>right = new TreeNode(7);
輸出
17
更新於：2020年10月21日
120 次檢視
廣告