513. 找树左下角的值

点此跳转题目链接

题目描述

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

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

示例 1:

在这里插入图片描述

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

示例 2:

在这里插入图片描述

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

提示:

  • 二叉树的节点个数的范围是 [1,104]
  • -231 <= Node.val <= 231 - 1

题解

题目说的很清楚了,目标先是 “最底层” ,再是 “最左边” ,所以考虑先用层序遍历得到最底层的节点值数组,然后返回数组第一个值,即为“左下角”的值了:

vector<vector<int>> levelOrder(TreeNode *root)
{
    vector<vector<int>> res;
    queue<TreeNode *> q;
    if (!root)
        return res;
    q.push(root);
    while (!q.empty())
    {
        int size = q.size(); // 注意!先记录当前队长,因为之后会变
        vector<int> level;   // 当前这一层的节点值
        for (int i = 0; i < size; ++i)
        {
            level.push_back(q.front()->val);
            if (q.front()->left)
                q.push(q.front()->left);
            if (q.front()->right)
                q.push(q.front()->right);
            q.pop();
        }
        res.push_back(level);
    }
    return res;
}

int findBottomLeftValue(TreeNode *root)
{
    vector<vector<int>> levels = levelOrder(root); // 偷个懒,直接调用之前写过的层序遍历函数
    return levels[levels.size() - 1][0];
}

此外,我们还是可以考虑一下递归法,逐步递归到左下角。递归出口的判断也比较简单,即:若当前节点的左孩子是叶子节点,则根据其深度判断是否要更新左下角值:

int maxDepth = -1;
int leftBottonVal = 0;

void traversal(TreeNode *root, int depth)
{
    // 递归出口:叶子节点
    if (!root->left && !root->right && depth > maxDepth)
    {
        leftBottonVal = root->val; // 更新当前探索到的左下角值
        maxDepth = depth;          // 更新当前探索到的最大深度
        return;
    }
    // 先处理左孩子,这样保证同一层记录最左节点
    if (root->left)
        traversal(root->left, depth + 1);
    // 再处理右孩子
    if (root->right)
        traversal(root->right, depth + 1);
}

int findBottomLeftValue_II(TreeNode *root)
{
    traversal(root, 0);
    return leftBottonVal;
}

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
解释:由于树是空的,所以不存在根节点到叶子节点的路径。

提示:

  • 树中节点的数目在范围 [0, 5000]
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

题解

首先可以用DFS递归秒杀:

bool hasPathSum(TreeNode *root, int targetSum)
{
    // 递归出口1:空节点
    if (!root)
        return false;
    // 递归出口2:加上当前节点值求和等于targetSum,且当前节点为叶子节点
    if (root->val == targetSum && !root->left && !root->right)
        return true;
    // 递归探索左右子树
    return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}

然后再想想迭代法,发现这题和 257. 二叉树的所有路径 其实如出一辙(具体思路和注意细节见那篇题解),只需要将其中记录路径的逻辑替换成计算路径节点值之和就行了:

bool hasPathSum_II(TreeNode *root, int targetSum) {
    // 基于前序遍历的统一迭代法实现
    if (!root)
        return false;
    stack<TreeNode*> nodeSt;
    nodeSt.push(root);
    stack<int> sumSt;
    sumSt.push(root->val);
    while (!nodeSt.empty()) {
        TreeNode *node = nodeSt.top();
        nodeSt.pop();
        int sum = sumSt.top(); 
        sumSt.pop();
        if (node) {
            if (node->right) {
                nodeSt.push(node->right); // 右
                sumSt.push(sum + node->right->val);
            }
            if (node->left) {
                nodeSt.push(node->left); // 左
                sumSt.push(sum + node->left->val);
            }
            nodeSt.push(node); // 中
            nodeSt.push(nullptr); // 空指针标记
            sumSt.push(sum);
        }
        else {
            if (sum == targetSum && !nodeSt.top()->left && !nodeSt.top()->right)
                return true;
            nodeSt.pop();
        }
    }
    return false;
}

106. 从中序和后序遍历序列构造二叉树

点此跳转题目链接

题目描述

给定两个整数数组 inorderpostorder ,其中 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]

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorderpostorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

题解

蛮锻炼思维的一道题目

我觉得核心是要理解两点:

1️⃣ 中序序列 inorder 的第 i 个值对应的节点,其左、右子树中的节点对应的就是 i 左边、右边的序列

2️⃣ 后序序列 postorder 的最后一个值,就是该序列对应的二叉树的根节点

这两点不难由中序遍历和后序遍历的定义和性质得出。于是,我们可以据此从根节点递归地“生长”出二叉树:

  • postorder 的最后一个值 r 为根节点 root 的值

  • inorder 中找到 r 对应的下标 i ,则 i 左边的值就对应着 root 的左子树、 i 右边的值就对应着 root 的右子树

    题目说了:inorderpostorder 都由 不同 的值组成,所以可以根据数值(唯一)对应去找下标

  • i 为“分割点”,将 inorder 拆分为左右两部分;相应地也将 postorder 拆分,满足

    • 排除 postorder 的最后一个值(因为它是分割点,对应着当前根节点)
    • postorder 的左右部分长度和 inorder 的左右部分长度相同
  • 按照上述方法递归地生成 root 的左右子树,递归出口为序列切片已经不可分割则返回空指针

此思路更详细的分析可参阅 代码随想录此题讲解 。我的代码如下,包括了一个调试函数 log ,用于debug的时候检查每次生成的中序、后序左右子序列长度是否一致、数值是否一一对应(即它们都表示着同一棵子树):

class Solution
{
private:
    // 由于所有值各不相同,先用哈希表存储其在中序、后序数组中的下标
    unordered_map<int, int> inMap, postMap;
    void getIndexMap(const vector<int> &inorder, const vector<int> &postorder)
    {
        for (int i = 0; i < inorder.size(); ++i)
        {
            inMap[inorder[i]] = i;
            postMap[postorder[i]] = i;
        }
    }

    // todo debug
    void log(
        const vector<int> &inorder, const vector<int> &postorder,
        int inLeftB, int inLeftE, int inRightB, int inRightE,
        int postLeftB, int postLeftE, int postRightB, int postRightE)
    {
        cout << "----------inorder left----------" << endl;
        for (int i = inLeftB; i < inLeftE; ++i)
            cout << inorder[i] << " ";
        cout << endl;

        cout << "---------postorder left---------" << endl;
        for (int i = postLeftB; i < postLeftE; ++i)
            cout << postorder[i] << " ";
        cout << endl;

        cout << "----------inorder right---------" << endl;
        for (int i = inRightB; i < inRightE; ++i)
            cout << inorder[i] << " ";
        cout << endl;

        cout << "-----------post right-----------" << endl;
        for (int i = postRightB; i < postRightE; ++i)
            cout << postorder[i] << " ";
        cout << endl;

        cout << "********************************" << endl;
    }

public:
    /// @brief 根据中序、后序数组的切片(左闭右开),递归获取树中的节点
    /// @param postorder 后序遍历数组(用于初始化当前的新节点)
    /// @param inBegin 当前中序数组的起始指针
    /// @param inEnd 当前中序数组的结尾指针
    /// @param postBegin 当前后序数组的起始指针
    /// @param postEnd 当前后序数组的结尾指针
    /// @return 当前获得的节点
    TreeNode *getNode(
        const vector<int> &inorder, const vector<int> &postorder,
        int inBegin, int inEnd, int postBegin, int postEnd)
    {
        if (inBegin == inEnd)
            return nullptr;

        // 后序数组的最后一个值,就是当前子树根节点的值
        TreeNode *root = new TreeNode(postorder[postEnd - 1]);

        // 定位该节点在中序数组中的位置,作为分割点
        int cutPoint = inMap[root->val];

        // 将中序数组拆分,则root的左右子树对应节点值也就是拆分后的左右部分
        int leftInBegin = inBegin, leftInEnd = cutPoint;     // 左半部分
        int rightInBegin = cutPoint + 1, rightInEnd = inEnd; // 右半部分

        // 相应的,将后序数组也按照同样位置拆分
        int leftPostBegin = postBegin, leftPostEnd = postBegin + (cutPoint - inBegin);     // 左半部分
        int rightPostBegin = postBegin + (cutPoint - inBegin), rightPostEnd = postEnd - 1; // 右半部分

        // log(
        //     inorder, postorder,
        //     leftInBegin, leftInEnd, rightInBegin, rightInEnd,
        //     leftPostBegin, leftPostEnd, rightPostBegin, rightPostEnd
        // );

        // 获取当前root的左右子树,然后返回当前root
        root->left = getNode(
            inorder, postorder, leftInBegin, leftInEnd, leftPostBegin, leftPostEnd);
        root->right = getNode(inorder, postorder, rightInBegin, rightInEnd, rightPostBegin, rightPostEnd);

        return root;
    }

    // 递归、多指针解决
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        getIndexMap(inorder, postorder);
        return getNode(inorder, postorder, 0, inorder.size(), 0, postorder.size());
    }
};

上面的写法比较便于理解算法和调试,将 log 那部分代码注释取消,运行题目描述中的示例1,可以看到每次递归生成的子序列。以第一次分割为例,有输出:

----------inorder left----------
9
---------postorder left---------
9
----------inorder right---------
15 20 7
-----------post right-----------
15 7 20
********************************
...

可以看到,中序、后序的左、右子序列都是一一对应的。

实际上,后序遍历的左右子序列没必要每次都全部维护,可以发现代码中我们实际用到的也就是其尾指针(每次指向当前的根节点)。所以可以简化代码如下(来源:LeetCode官方题解):

class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
        // 如果这里没有节点构造二叉树了,就结束
        if (in_left > in_right) {
            return nullptr;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];

        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;

        // 建立(元素,下标)键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};

作者:力扣官方题解
链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solutions/426738/cong-zhong-xu-yu-hou-xu-bian-li-xu-lie-gou-zao-14/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部