我做的网站上有需要别人直接下载的东西 怎么做到这一步,东莞seo整站优化,怎么做图片网站源码,设计封面题目描述
给定二叉树的根节点 root #xff0c;返回所有左叶子之和。
题目分析
其实这题无论是迭代法还是递归法#xff0c;最重要的是要明确判断左叶子的条件#xff1a;当前节点有左孩子#xff0c;且这个左孩子没有它的左孩子和右孩子。
迭代法
感觉只要二叉树相关…题目描述
给定二叉树的根节点 root 返回所有左叶子之和。
题目分析
其实这题无论是迭代法还是递归法最重要的是要明确判断左叶子的条件当前节点有左孩子且这个左孩子没有它的左孩子和右孩子。
迭代法
感觉只要二叉树相关的题递归想不出来直接暴力上层序遍历就能解出来。迭代法真没什么难度就是把内层while循环中处理当前节点的条件换成上面的逻辑就行也即
if(node-left node-left-leftNULL node-left-right NULL) sum node-left-val;整体cpp代码
/*** 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:int sumOfLeftLeaves(TreeNode* root) {// 迭代法层序遍历queueTreeNode* q;int sum 0;if(root!NULL) q.push(root);while(!q.empty()){int size q.size();while(size--){TreeNode* node q.front();q.pop();if(node-left node-left-leftNULL node-left-right NULL) sum node-left-val;if(node-left) q.push(node-left);if(node-right) q.push(node-right);}}return sum;}
};递归法
这里我和代码随想录中处理的不太一样但是思路是一样的。我这里用了传出参数vectorint sum所以我用什么遍历顺序都是对的。但是代码随想录中是用了int返回值所以是要从下层传结果送至上层汇聚那么这就必须要用后序遍历左右中。
我的cpp整体递归代码
注意这里中左右的顺序可以任意变换已经试过了都能AC。
/*** 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:void traversal(TreeNode* cur, vectorint sum){// 递归终止条件if(cur NULL) return;if(cur-left) traversal(cur-left, sum);if(cur-right) traversal(cur-right, sum);// 单层递归逻辑当该节点只有一个左孩子左叶子if(cur-left!NULL cur-left-leftNULL cur-left-rightNULL){sum.push_back(cur-left-val);}}int sumOfLeftLeaves(TreeNode* root) {// 递归法vectorint sum;traversal(root, sum);return accumulate(sum.begin(), sum.end(), 0);}
};代码随想录的cpp整体递归代码
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root NULL) return 0;if (root-left NULL root-right NULL) return 0;int leftValue sumOfLeftLeaves(root-left); // 左if (root-left !root-left-left !root-left-right) { // 左子树就是一个左叶子的情况leftValue root-left-val;}int rightValue sumOfLeftLeaves(root-right); // 右int sum leftValue rightValue; // 中return sum;}
};
