C++刷题之旅（43）

层序遍历，每一个深度下的最右值，即为可以看到的点。

class Solution {
public:
    vector rightSideView(TreeNode* root) {
        unordered_map rightmostValueAtDepth;
        int max_depth = -1;

        queue nodeQueue;
        queue depthQueue;
        nodeQueue.push(root);
        depthQueue.push(0);

        while (!nodeQueue.empty()) {
            TreeNode* node = nodeQueue.front();nodeQueue.pop();
            int depth = depthQueue.front();depthQueue.pop();

            if (node != NULL) {
            	// 维护二叉树的最大深度
                max_depth = max(max_depth, depth);

                // 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                rightmostValueAtDepth[depth] =  node -> val;

                nodeQueue.push(node -> left);
                nodeQueue.push(node -> right);
                depthQueue.push(depth + 1);
                depthQueue.push(depth + 1);
            }
        }

        vector rightView;
        for (int depth = 0; depth <= max_depth; ++depth) {
            rightView.push_back(rightmostValueAtDepth[depth]);
        }

        return rightView;
    }
};

class Solution {
public:
    vector path;   //存储路径
    vector> result;  //存储结果，可能不止一条路径符合要求

    void traversal(TreeNode* cur, int count){
        //找到叶子节点，且计数器为0，符合要求
        if(!cur->left && !cur->right && count == 0){   
            result.push_back(path);
            return;
        }
        //找到叶子节点，但计数器不为0，不符合要求
        if(!cur->left && !cur->right) return;
        //遍历左子树，先将节点值存入路径中，并将计数器减去节点值，如果到达叶子节点不符合要求，则返回上一层，计数器往回加上节点值，路径中弹出节点值实现回溯
        if(cur->left){
            path.push_back(cur->left->val);     
            count -= cur->left->val;
            traversal(cur->left, count);  //递归
            count += cur->left->val;  //回溯
            path.pop_back();    //回溯
        }
        if(cur->right){
            path.push_back(cur->right->val);
            count -= cur->right->val;
            traversal(cur->right, count);
            count += cur->right->val;
            path.pop_back();
        }
        return;
    }

    vector> pathSum(TreeNode* root, int targetSum) {
        path.clear();
        result.clear();
        if(root == nullptr) return result;
        path.push_back(root->val);
        traversal(root, targetSum - root->val);   //传入目标值减去根节点值
        return result;
    }
};

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //终止条件
        if(root == nullptr) return nullptr;
        if(root->val == key){
            //左右孩子都为空
            if(root->left == nullptr && root->right == nullptr){
                return nullptr;
            }
            //左孩子不为空，右孩子为空，删除节点，返回左孩子为节点
            else if(root->right == nullptr){
                root = root->left;
                return root;
            }
            //左孩子为空，右孩子不为空，删除节点，返回右孩子为节点
            else if(root->left == nullptr){
                root = root->right;
                return root;
            }
            //左右孩子都不为空，将节点的左孩子接到右孩子的最左节点，然后删除节点，返回节点的右孩子作为节点
            else{
                TreeNode* tmp = root;
                TreeNode* cur = root->right;
                while(cur->left != nullptr){   //找到节点右子树的最左侧
                    cur = cur->left;
                }
                cur->left = root->left;   //将节点的左子树接到节点右子树的最左侧
                root = tmp->right;      //节点右孩子为新的节点
                delete tmp;     //释放临时变量
                return root;
            }
        }
        if(root->val > key) root->left = deleteNode(root->left, key);   //节点值大于key，往左孩子找
        if(root->val < key) root->right = deleteNode(root->right, key);

        return root;
    }
};