代码随想录打卡Day16

标签：right TreeNode 随想录 Day16 打卡 left root 节点 postorder

1.力扣531:找树左下角的值。

题目描述:

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

解答代码:

/**
 * 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 max_Depth = INT_MIN;    // 全局变量,最大深度
    int result;                 // 全局变量,最大深度左节点的值

    // 1.确定参数和返回值
    void traversal(TreeNode* root, int depth) {
        // 2.终止条件
        if (root->left == NULL && root->right == NULL) {
            if (depth > max_Depth) {
                max_Depth = depth;
                result = root->val;
            }
        }

        // 3.单层递归的逻辑
        if (root->left) {
            depth ++;
            traversal(root->left, depth);
            depth --;   // 回溯
        }

        if (root->right) {
            depth ++;
            traversal(root->right, depth);
            depth --;
        }
    }

    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

代码逻辑:

代码用于查找二叉树最底层最左边的节点值。其关键逻辑是使用递归遍历树的所有节点，同时记录当前节点的深度，并在到达叶子节点时更新最大深度和对应节点值。

代码详解

1. 全局变量：
- 'max_Depth'：记录当前访问到的最大深度，初始值为 'INT_MIN'。
- 'result'：记录最大深度的最左侧节点的值。

2. 递归函数 'traversal(TreeNode root, int depth)'：
- 参数：
- 'root'：当前节点。
- 'depth'：当前节点的深度。
- 终止条件：
- 'if (root->left == NULL && root->right == NULL)'：当到达叶节点时，比较当前深度 'depth' 与 'max_Depth'，如果当前深度更大，则更新 'max_Depth' 和 'result'，保存当前节点值为最左下角的值。
- 递归逻辑：
- 对当前节点的左子节点和右子节点分别进行递归调用。
- 在递归调用前增加 'depth'，在递归返回后通过 'depth--' 回溯，这样可以保证不同路径上的深度记录不会相互影响。

3. 主函数 'findBottomLeftValue(TreeNode root)'：
- 初始化调用 'traversal(root, 0)' 开始遍历，初始深度为 0。
- 返回 'result'，即树底层最左边的节点值。

代码的回溯操作

在单层递归中，当遍历完左或右子树时，通过 'depth--' 进行回溯，确保每次递归调用的 'depth' 参数准确反映当前节点的深度，不影响其他路径的计算。

2.力扣112:路径总和。

题目描述:

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。

解答代码:

/**
 * 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:
    bool traversal(TreeNode* root, int count) {
        if (root->left == NULL && root->right == NULL && count == 0) {
            return true;
        }

        if (root->left == NULL && root->right == NULL && count != 0) {
            return false;
        }

        if (root->left) {
            count -= root->left->val;
            if (traversal(root->left, count))
            {
                return true;
            }
            count += root->left->val;
        }

        if (root->right) {
        count -= root->right->val;
            if (traversal(root->right, count))
            {
                return true;
            }
            count += root->right->val;
        }
        return false;
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        return traversal(root, targetSum - root->val);
    }
};

代码逻辑:

这段代码用于判断二叉树中是否存在一条从根节点到叶节点的路径，使得路径上节点值的和等于给定的 'targetSum'。它通过递归遍历树的所有路径，逐步减去当前节点的值，来判断是否达成目标和。

代码详解

1. 递归函数 'traversal(TreeNode root, int count)'：
- 参数：
- 'root'：当前节点。
- 'count'：目标和减去当前路径上节点值后的剩余和。
- 终止条件：
- 'if (root->left == NULL && root->right == NULL && count == 0)'：当到达叶节点且 'count' 为 0 时，说明找到一条满足条件的路径，返回 'true'。
- 'if (root->left == NULL && root->right == NULL && count != 0)'：当到达叶节点但 'count' 不为 0 时，说明该路径不满足条件，返回 'false'。
- 递归逻辑：
- 对当前节点的左子节点和右子节点分别进行递归调用。
- 在递归调用前减去当前节点值，从而更新 'count'，当递归返回后将 'count' 恢复原值（回溯操作），保证其他路径不受影响。

2. 主函数 'hasPathSum(TreeNode root, int targetSum)'：
- 判断 'root' 是否为空，若为空直接返回 'false'。
- 调用 'traversal(root, targetSum - root->val)' 开始递归遍历，初始时 'count' 为 'targetSum' 减去 'root' 节点的值。

回溯操作

在递归中，'count' 被减去当前节点的值以传递给下一层递归，并在递归返回后恢复，以确保同一层的不同子路径互不影响。

3.力扣106:从中序与后序遍历构造二叉树。

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

题目描述:

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

解答代码:

/**
 * 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:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;

        int rootVal = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootVal);

        if (postorder.size() == 1) return root;

        int index;
        for (index = 0; index < inorder.size(); index++) {
            if (inorder[index] == rootVal) break;
        }

        vector<int> leftInorder(inorder.begin(), inorder.begin() + index);
        vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());


        postorder.resize(postorder.size() - 1);
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }


    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

代码逻辑:

这段代码通过递归构建二叉树，基于给定的中序遍历（'inorder'）和后序遍历（'postorder'）数组。
核心逻辑
- 二叉树的后序遍历的特点是根节点在最后，所以'postorder[postorder.size() - 1]'就是当前树的根节点。
- 中序遍历的特点是：根节点左侧的元素构成左子树，右侧的元素构成右子树。因此，通过在 'inorder' 数组中找到根节点的位置 'index'，可以将 'inorder' 分成左、右子树的两个部分。
- 递归分割 'inorder' 和 'postorder' 来构建树，直到满足递归的结束条件。

代码详解
1. 递归终止条件：
- 'if (postorder.size() == 0) return NULL;'：如果 'postorder' 数组为空，返回 'NULL'，表示空树。
- 'if (postorder.size() == 1) return root;'：当 'postorder' 数组仅有一个元素时，返回当前节点，代表已经到达叶节点，不再进行分割。

2. 找到根节点并分割数组：
- 'int rootVal = postorder[postorder.size() - 1];'：后序遍历数组的最后一个元素是当前树的根节点。
- 通过循环找到 'rootVal' 在 'inorder' 数组中的位置 'index'。
- 使用 'index' 将 'inorder' 分割为左右子树的 'inorder' 序列，并相应地分割 'postorder' 序列。

3. 递归构造左右子树：
- 'root->left = traversal(leftInorder, leftPostorder);'：递归构造左子树。
- 'root->right = traversal(rightInorder, rightPostorder);'：递归构造右子树。

4. 构造完成后返回根节点：
- 返回已构建的子树根节点，递归完成整个树的构造。

终止条件:

'if (postorder.size() == 1) return root;' 的作用是处理递归中的终止条件，当 'postorder' 数组只有一个元素时，即树只有一个节点的情况下直接返回该节点作为根节点。这确保了递归不会继续深入，避免了不必要的计算和数组分割。

在这种情况下：

1. 'postorder.size() == 1' 说明当前递归调用已经到达了叶子节点（树的最底层），不需要再进一步划分。
2. 'root' 是使用唯一的值 'postorder[postorder.size() - 1]' 创建的叶子节点，它没有左右子树，因此直接返回这个节点，递归回溯到上一层。

这句条件判断起到了优化递归效率的作用，使得递归能够正确、快速地在叶子节点处结束。

标签：right,TreeNode,随想录,Day16,打卡,left,root,节点,postorder
From： https://blog.csdn.net/jianbaigreat/article/details/143463983

1.力扣531:找树左下角的值。

题目描述:

解答代码:

代码逻辑:

2.力扣112:路径总和。

题目描述:

解答代码:

代码逻辑:

3.力扣106:从中序与后序遍历构造二叉树。

题目描述:

解答代码:

代码逻辑:

终止条件:

相关文章

赞助商

阅读排行