数据结构
网络
关系数据库管理系统(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 次查看
广告