代码随想录算法训练营第18天 | 513.找树左下角的值, 112. 路径总和, 113.路径总和ii, 105.从前序与中序遍历序列构造二叉树, 106.从中序与后序遍历序列构造二叉树

513.找树左下角的值

代码随想录链接

题目

给定一颗二叉树, 返回树的最后一层的最左侧叶子结点的值.

自己的想法

迭代法的话就层序遍历, 判断当前访问的一层是否都是叶子节点, 若是, 则输出该层第一个节点的值.

递归法的话就要使用前序遍历了, 在不断往下遍历时, 标记最深的叶子节点.

题解

迭代法:

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int result = 0;
        queue<TreeNode *> que;
        if (!root) return result;
        que.push(root);
        while (!que.empty()) {
            int qsize = que.size();
            bool hasChild = false;
            result = que.front() -> val;    // 取该层最左侧节点的值
            for (int i = 0; i < qsize; i++) {
                TreeNode *node = que.front();
                que.pop();
                if (node -> left) {
                    hasChild = true;
                    que.push(node -> left);
                }
                if (node -> right) {
                    hasChild = true;
                    que.push(node -> right);
                }
            }
            if (!hasChild) return result;   // 如果本层节点都没有子节点, 则返回本层第一个节点的值
        }
        return result;
    }
};

递归法:

class Solution {
private:
    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); // 递归遍历右子树
    }
public:
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return this -> result;
    }
};

112. 路径总和 113.路径总和ii

代码随想录链接

题目

112题是只要求判断是否有路径之和等于给定值, 而113题要求输出这些路径, 除此之外没有区别.

自己的想法

迭代法的话使用前序遍历, 存储根节点到当前节点的值, 进行判断

递归法同样是使用前序遍历.

题解

112 递归法:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        if (!(root -> left) && !(root -> right) && targetSum == root -> val) return true;   // 判断当前节点是否符合
        return hasPathSum(root -> left, targetSum - root -> val) || hasPathSum(root -> right, targetSum - root -> val);     // 将给定值减去当前节点的值, 并递归判断左孩子和右孩子
    }
};

112 迭代法:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        stack<pair<TreeNode*, int>> st;   // 存储根节点到当前节点的值的栈
        st.push(pair<TreeNode*, int>(root, root -> val));
        while (!st.empty()) {
            auto node = st.top();
            st.pop();
            if (!(node.first -> left) && !(node.first -> right) && node.second == targetSum) return true;   // 判断当前取出的节点是否符合
            if (node.first -> left) st.push(pair<TreeNode*, int>(node.first -> left, node.second + node.first -> left -> val)); // 将左孩子与左孩子的路径值入栈
            if (node.first -> right) st.push(pair<TreeNode*, int>(node.first -> right, node.second + node.first -> right ->val));   // 将右孩子与右孩子的路径值入栈
        }
        return false;
    }
};

113 迭代法:

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        if (!root) return result;
        vector<vector<int>> paths;      // 存放节点的路径, 换成栈也可以
        stack<pair<TreeNode*, int>> st; // 存放节点和到达它的路径值
        st.push(pair<TreeNode*, int>(root, root -> val));
        paths.push_back(vector<int>{root -> val});
        while (!st.empty()) {
            auto node = st.top(); st.pop();
            auto path = paths.back(); paths.pop_back();

            if (!(node.first -> left) && !(node.first -> right) && node.second == targetSum) result.push_back(path);    // 如果当前取出的节点符合条件, 就将路径记录在结果数组里

            if (node.first -> left) {   // 左孩子的相关信息记录下来
                st.push(pair<TreeNode*, int>(node.first -> left, node.second + node.first -> left -> val));
                path.push_back(node.first -> left -> val);
                paths.push_back(path);
                path.pop_back();
            }

            if (node.first -> right) {  // 右孩子的相关信息记录下来
                st.push(pair<TreeNode*, int>(node.first -> right, node.second + node.first -> right -> val));
                path.push_back(node.first -> right -> val);
                paths.push_back(path);
            }
        }
        return result;
    }
};

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

代码随想录链接

题目

根据二叉树的中序和后序遍历构建二叉树

根据二叉树的前序和中序遍历构建二叉树

自己的想法

对于给定中序和后序的情况, 先使用后序的最后一个确定根节点, 然后根据根节点, 在中序数组中划分出来左字数的中序和右子树的中序, 又因为同一棵子树的节点数目是相同的, 也能在后序遍历的数组当中划分出左子树的后序遍历以及右子树的后序遍历. 根据左右子树的两种遍历数组, 递归地进行构建即可.

对于给定前序和中序的情况, 和上面是相似的, 进行划分, 得到左右子树的前序和中序遍历, 再进行递归即可.

题解

105:

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() != preorder.size()) return NULL;
        if (!inorder.size()) return NULL;
        int rootVal = preorder.front();
        TreeNode *root = new TreeNode(rootVal);

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

        int rootValIndex;
        for (rootValIndex = 0; rootValIndex < inorder.size(); rootValIndex++)   // 找到根节点的位置, 以进行划分
            if (inorder[rootValIndex] == rootVal)
                break;
        
        vector<int> leftInOrder(inorder.begin(), inorder.begin() + rootValIndex);   // 划分左右子树的前序和中序
        vector<int> rightInOrder(inorder.begin() + rootValIndex + 1, inorder.end());
        vector<int> leftPreOrder(preorder.begin() + 1, preorder.begin() + rootValIndex + 1);
        vector<int> rightPreOrder(preorder.begin() + rootValIndex + 1, preorder.end());
        root -> left = buildTree(leftPreOrder, leftInOrder);    // 递归构建左右子树
        root -> right = buildTree(rightPreOrder, rightInOrder);

        return root;
    }
};

106:

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() != postorder.size()) return NULL;
        if (!inorder.size()) return NULL;
        int rootVal = postorder.back();
        TreeNode *root = new TreeNode(rootVal);

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

        int rootValIndex;
        for (rootValIndex = 0; rootValIndex < inorder.size(); rootValIndex++)   // 定位根节点, 以进行划分
            if (inorder[rootValIndex] == rootVal)
                break;
        
        vector<int> leftInOrder(inorder.begin(), inorder.begin() + rootValIndex);   // 划分左右子树的中序和后序
        vector<int> rightInOrder(inorder.begin() + rootValIndex + 1, inorder.end());
        vector<int> leftPostOrder(postorder.begin(), postorder.begin() + rootValIndex);
        vector<int> rightPostOrder(postorder.begin() + rootValIndex, postorder.end() - 1);
        root -> left = buildTree(leftInOrder, leftPostOrder);   // 递归构建左右子树
        root -> right = buildTree(rightInOrder, rightPostOrder);

        return root;
    }
};