首页 计算机科学 算法 LeetCode

# 找树左下角的值

题目链接🔗

# 迭代

层序遍历找最后一行第一个值。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != nullptr) 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;
    }
};

# 递归

使用递归判断是否是最后一行，其实就是看找深度最大的子叶节点。

如何判断最左边的节点？递归时保证优先左边搜索，然后记录深度最大的子叶节点，此时就是树的最后一行最左边的值。

  1. 确定递归函数的参数和返回值

参数必须有要遍历的树的根节点，还有就是一个 int 型的变量用来记录最长深度。

还需要类里的两个全局变量，maxLen 用来记录最大深度，result 记录最大深度最左节点的数值。

  1. 确定终止条件

当遇到叶子节点的时候，就需要统计一下最大深度。所以终止条件就是遇到叶子节点。

  1. 确定单层递归的逻辑

找最大深度的时候依然使用回溯。

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == nullptr && root->right == nullptr) {
            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;
    }
};

# 路径总和

题目链接🔗

要遍历从根节点到叶子节点的路径看总和是否等于目标和，可以用 DFS 遍历。

DFS遍历

  1. 确定递归函数的参数和返回值

参数需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和，用以是否正好是目标和。

遍历并不需要遍历整棵树，所以需要返回值。

  1. 确定终止条件

首先计数器如何统计这一条路径的和呢？

不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器 count 初始为目标和，然后每次减去遍历路径节点上的数值。

如果最后count==0count == 0，同时到了叶子节点的话，说明找到了目标和。

如果遍历到了叶子节点，count 不为 0，就是没找到。

  1. 确定单层递归逻辑

因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。

递归函数是有返回值的，如果递归函数返回 true，说明找到了合适的路径，应该立刻返回。

class Solution {
private:
    bool traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为 0
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
        if (cur->left) { // 左
            count -= cur->left->val; // 递归，处理节点；
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯，撤销处理结果
        }
        if (cur->right) { // 右
            count -= cur->right->val; // 递归，处理节点；
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯，撤销处理结果
        }
        return false;
    }
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        return traversal(root, targetSum - root->val);
    }
};
# 从中序遍历和后序遍历构造二叉树
题目链接🔗
以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
流程如图：
中序和后序构造二叉树
递归分为以下几步：
  1. 如果数组为空，是空节点。
  2. 如果数组不为空，取数组最后一个元素为节点元素。
  3. 找到后续数组第一个元素在中序数组的位置，作为切割点。
  4. 切割中序数组，切成中序左数组和右数组。
  5. 切割后序数组，切成后序左数组和右数组。
  6. 递归处理左区间和右区间。
TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
    // 第一步
    if (postorder.size() == 0) return nullptr;
    // 第二步：后序遍历数组最后一个元素，就是当前的中间节点
    int rootValue = postorder[postorder.size() - 1];
    TreeNode* root = new TreeNode(rootValue);
    // 叶子节点
    if (postorder.size() == 1) return root;
    // 第三步：找切割点
    int delimiterIndex;
    for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
        if (inorder[delimiterIndex] == rootValue) break;
    }
    // 第四步：切割中序数组，得到 中序左数组和中序右数组
    // 第五步：切割后序数组，得到 后序左数组和后序右数组
    // 第六步
    root->left = traversal(中序左数组, 后序左数组);
    root->right = traversal(中序右数组, 后序右数组);
    return root;
}
切割一定要确定区间的标准。是左闭右开，还有左开右闭，还是左闭右闭，这个就是不变量，要在递归中保持这个不变量。
中序数组很好切割，而后序数组没有明确的切割点。
但是，中序数组大小一定是和后序数组大小相同，因此可以用中序数组的 size 来切割后序数组。
class Solution {
private:
    // 中序区间：[inorderBegin, inorderEnd)，后序区间 [postorderBegin, postorderEnd)
    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
        if (postorderBegin == postorderEnd) return nullptr;
        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);
        if (postorderEnd - postorderBegin == 1) return root;
        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 左中序区间，左闭右开 [leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 右中序区间，左闭右开 [rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;
        // 切割后序数组
        // 左后序区间，左闭右开 [leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小 size
        // 右后序区间，左闭右开 [rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (delimiterIndex - 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 nullptr;
        // 左闭右开的原则
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};
# 最大二叉树
题目链接🔗
最大二叉树
构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
  1. 确定递归函数的参数和返回值
参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点。
  1. 确定终止条件
题目中说了输入的数组大小一定是大于等于 1 的，所以不用考虑小于 1 的情况，当递归遍历的时候，如果传入的数组大小为 1，说明遍历到了叶子节点了。
那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是 1 的时候，构造了一个新的节点，并返回。
  1. 确定单层递归的逻辑
  • 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
  • 最大值所在的下标左区间构造左子树。
  • 最大值所在的下标右区间构造右子树。
class Solution {
private:
    // 在左闭右开区间 [left, right)，构造二叉树
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left >= right) return nullptr;
        // 分割点下标：maxValueIndex
        int maxValueIndex = left;
        for (int i = left + 1; i < right; ++i) {
            if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
        }
        // 中间节点
        TreeNode* root = new TreeNode(nums[maxValueIndex]);
        // 构造左子树，左闭右开：[left, maxValueIndex)
        root->left = traversal(nums, left, maxValueIndex);
        // 构造右子树，左闭右开：[maxValueIndex + 1, right)
        root->right = traversal(nums, maxValueIndex + 1, right);
        return root;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
};