Day21 404左叶子之和 513找树左下角的值

本文主要是介绍Day21 404左叶子之和 513找树左下角的值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        首先要明白如何判断出一个结点是不是左叶子，要从父节点来判断，如果这个父节点的左孩子不为空，左孩子的左孩子和左孩子的有孩子都为空，就说明他的左孩子是左叶子了。如果用递归法，主要是单层递归逻辑那里需要多加考虑，本题利用后序的方法比较好，左右中，首先往左进行遍历，判断一下是否是左叶子，之后右递归遍历，最后中间节点（父节点）加和。

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;}
};

        本代码可以进行精简，其实也比较好理解：        

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root == NULL) return 0;int leftValue = 0;if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {leftValue = root->left->val;}return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);}
};

         当然，本题也可以采用迭代法，这里我采用比较熟悉的层序：

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {queue<TreeNode*> que;if(root != nullptr) que.push(root);int sum = 0;while(!que.empty()){int size = que.size();while(size--){TreeNode* node = que.front();que.pop();if(node->left && !node->left->left && !node->left->right){sum += node->left->val;}if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return sum;}
};

                平时我们解二叉树的题目时，已经习惯了通过结点的左右孩子判断本节点的属性，二本题我们要通过结点的父节点判断本节点的属性，属于是拓宽了思路。

513 找树左下角的值

给定一个二叉树，在树的最后一行找到最左边的值。

首先想到的一定是迭代遍历里的层序，和之前那道找最右边结点很像。

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result = 0;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (i == 0) result = node->val; // 记录最后一行第一个元素if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

         但是本题最好还是要再训练一下递归法：如果一直向左遍历到最后一个，不一定是最终的答案，因为他未必是最后一行。那么如何判断是最后一行呢，其实就是深度最大的叶子节点。既然要找到最左边，那么只要保证优先左边搜索，记录深度最大的叶子节点即可。

        定义两个全局变量，maxdepth记录最大深度，result记录最大深度最左节点的数值。当遇到叶子结点的时候，就需要统计一下最大深度了，同时，本题还需要使用回溯，如果不回溯的话，高度就会一直递增错误。

class Solution {
public:int maxDepth = INT_MIN;int result;void traversal(TreeNode* root, int depth) {if (root->left == NULL && root->right == NULL) {if (depth > maxDepth) {maxDepth = depth;result = root->val;}return;}if (root->left) {depth++;traversal(root->left, depth);depth--; // 回溯}if (root->right) {depth++;traversal(root->right, depth);depth--; // 回溯}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};

        当然回溯过程也可以简化，和上次的回溯简化其实类似：

class Solution {
public:int maxDepth = INT_MIN;int result;void traversal(TreeNode* root, int depth) {if (root->left == NULL && root->right == NULL) {if (depth > maxDepth) {maxDepth = depth;result = root->val;}return;}if (root->left) {traversal(root->left, depth + 1); // 隐藏着回溯}if (root->right) {traversal(root->right, depth + 1); // 隐藏着回溯}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};

这篇关于Day21 404左叶子之和 513找树左下角的值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---