算法训练day18 LeetCode 513.112.106

513.找树左下角的值

题目

513. 找树左下角的值 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

递归方式

单独数据存储最大深度，和此深度的结点值
递归后要注意回溯

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

迭代法
使用层序遍历

记录每一层的第一个元素

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

112.路径总和

题目

112. 路径总和 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

递归方法（寻找根节点到叶子节点的路径）

使用计数器count逐个减去节点的值，而不使用求和再比较的方法以简化代码
回溯寻找新路径
设置函数传入值可以简化代码

class Solution
{
private:
    bool traversal(TreeNode *cur, int count)
    {
        if (!cur->left && !cur->right && count == 0)
            return true;
        if (!cur->left && !cur->right && count != 0)
            return false;

        if (cur->left)
        {
            if (traversal(cur->left, count - cur->left->val))
                return true;
        }
        if (cur->right)
        {
            if (traversal(cur->right, count - cur->right->val))
                return true;
        }
        return false;
    }

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

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

题目

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

根据中序和后序遍历顺序特点，切割中序和后序数组
使用递归的方式不断地将层层地根节点组织起来
注意区间地选择（此处为左闭右开）

class Solution
{
private:
    TreeNode *traversal(vector<int> &inorder, int inorderBegin, int inorderEnd, vector<int> &postorder, int postorderBegin, int postorderEnd)
    {
        if (postorderBegin == postorderEnd)
            return NULL;

        int rootValue = postorder[postorderEnd - 1];
        TreeNode *root = new TreeNode(rootValue);

        if (postorderEnd - postorderBegin == 1)
            return root;

        int delimitetIndex;
        for (delimitetIndex = inorderBegin; delimitetIndex < inorderEnd; delimitetIndex++)
        {
            if (inorder[delimitetIndex] == rootValue)
                break;
        }

        // 切割中序数组 注意区间选择
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimitetIndex;
        int rightInorderBegin = delimitetIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割后序数组 注意区间选择
        int leftPostorderBegin = postorderBegin;
        int leftPostorderEnd = postorderBegin + (delimitetIndex - inorderBegin);
        int rightPostorderBegin = postorderBegin + (delimitetIndex - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1;

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
        return root;
    }

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