day16 二叉树4

513.找树左下角的值

迭代法：

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        deque<TreeNode*> q;
        q.push_back(root);
        int res;
        while (!q.empty()) {
            int n = q.size();
            res = q.front()->val;
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
        }
        return res;
    }
};

递归法：

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* node, int height) {
        if (node->left == nullptr && node->right == nullptr) {
            if (height > maxDepth) {
                maxDepth = height;
                result = node->val;
            }
            if (node->left) {
                traversal(node->left, height + 1);
            }
            if (node->right) {
                traversal(node->right, height + 1);
            }
        }
    }

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

112. 路径总和

class Solution {
public:
    bool result = false;
    void traversal(int targetSum, TreeNode *cur) {
        if (cur == nullptr) {
            return;
        }
        if (cur->val == targetSum && cur->left == nullptr && cur->right == nullptr) {
            result = true;
            return;
        }
        traversal(targetSum - cur->val, cur->left);
        traversal(targetSum - cur->val, cur->right);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        traversal(targetSum, root);
        return result;
    }
};

113. 路径总和ii

class Solution {
public:
    vector<vector<int>> res;
    void traversal(vector<int> &path, TreeNode *cur, int targetSum) {
        if (cur == nullptr) {
            return;
        }
        if (cur->left == nullptr && cur->right == nullptr && targetSum == 0) {
            res.push_back(path);
            return;
        }
        if (cur->left) {
            path.push_back(cur->left->val);
            traversal(path, cur->left, targetSum - cur->left->val);
            path.pop_back();
        }
        if (cur->right) {
            path.push_back(cur->right->val);
            traversal(path, cur->right, targetSum - cur->right->val);
            path.pop_back();
        }
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) {
            return res;
        }
        vector<int> path;
        path.push_back(root->val);
        traversal(path, root, targetSum - root->val);
        return res;
    }
};

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

很有思路，但是写不对。。。。

class Solution {
public:
    int findIndex(int val, vector<int> &inorder) {
        for (int i = 0; i < inorder.size(); i ++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

    TreeNode* traversal(vector<int> &inorder, vector<int> &postorder) {
        if (postorder.size() == 0) {
            return nullptr;
        }
        TreeNode* node = new TreeNode(postorder[postorder.size() - 1]);
        int index = findIndex(node->val, inorder);
        vector<int> leftInorder(inorder.begin(), inorder.begin() + index);
        vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + index);
        vector<int> rightPostorder(postorder.begin() + index, postorder.end() - 1);
        node->left = traversal(leftInorder, leftPostorder);
        node->right = traversal(rightInorder, rightPostorder);
        return node;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return traversal(inorder, postorder);
    }
};

以上写法，每次递归都定义了新的vector，既耗时又耗空间，优化版：

class Solution {
public:
    int getIndex(int val, vector<int> &inorder) {
        for (int index = 0; index < inorder.size(); index ++) {
            if (inorder[index] == val) {
                return index;
            }
        }
        return -1;
    }

    TreeNode* traversal(vector<int> &inorder, vector<int> &postorder, int inBegin, int inEnd, int postBegin, int postEnd) {
        if (inBegin >= inEnd || postBegin >= postEnd) {
            return nullptr;
        }
        TreeNode *node = new TreeNode(postorder[postEnd - 1]);
        int index = getIndex(postorder[postEnd - 1], inorder);
        int leftInBegin = inBegin;
        int leftInEnd = index;
        int leftPostBegin = postBegin;
        int leftPostEnd = postBegin + (index - inBegin);
        int rightInBegin = index + 1;
        int rightInEnd = inEnd;
        int rightPostBegin = postBegin + (index - inBegin);
        int rightPostEnd = postEnd - 1;
        node->left = traversal(inorder, postorder, leftInBegin, leftInEnd, leftPostBegin, leftPostEnd);
        node->right = traversal(inorder, postorder, rightInBegin, rightInEnd, rightPostBegin, rightPostEnd);
        return node;
    }

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

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

class Solution {
public:
    int getIndex(vector<int> &inorder, int val) {
        for (int index = 0; index < inorder.size(); index ++) {
            if (inorder[index] == val) {
                return index;
            }
        }
        return -1;
    }
    TreeNode* traversal(vector<int> &preorder, vector<int> &inorder) {
        if (preorder.size() == 0) {
            return nullptr;
        }
        TreeNode *node = new TreeNode(preorder[0]);
        int index = getIndex(inorder, preorder[0]);
        vector<int> leftPre(preorder.begin() + 1, preorder.begin() + index + 1);
        vector<int> rightPre(preorder.begin() + index + 1, preorder.end());
        vector<int> leftIn(inorder.begin(), inorder.begin() + index);
        vector<int> rightIn(inorder.begin() + 1 + index, inorder.end());
        node->left = traversal(leftPre, leftIn);
        node->right = traversal(rightPre, rightIn);
        return node;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return traversal(preorder, inorder);
    }
};

优化版：

class Solution {
public:
    int getIndex(vector<int> &inorder, int val) {
        for (int index = 0; index < inorder.size(); index ++) {
            if (inorder[index] == val) {
                return index;
            }
        }
        return -1;
    }
    TreeNode* traversal(vector<int> &preorder, vector<int> &inorder, int leftPre, int rightPre, int leftIn, int rightIn) {
        if (leftPre >= rightPre) {
            return nullptr;
        }
        TreeNode *node = new TreeNode(preorder[leftPre]);
        int index = getIndex(inorder, preorder[leftPre]);
        node->left = traversal(preorder, inorder, leftPre + 1, leftPre + 1 + (index - leftIn), leftIn, leftIn + (index - leftIn));
        node->right = traversal(preorder, inorder, leftPre + 1 + (index - leftIn), rightPre, index + 1, rightIn);
        return node;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        return traversal(preorder, inorder, 0, n, 0, n);
    }
};

关键是：确定好右边是不是闭区间，然后就一直按这个写，然后长度length搞清楚。