【代码随想录】第8章 二叉树（中）

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //2.确定单层终止条件
        if(root == nullptr) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int maxDepth(Node* root) {
        int res = 0;
        if(root == nullptr) return res;
        queue<Node*> q;
        q.push(root);
        while(!q.empty()){
            int currentSize = q.size();
            res++;
            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();
                for(auto j : node->children){
                    q.push(j);
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    int maxDepth(Node* root) {
        int res = 0;
        if(root == nullptr)  return res;
        for(auto node : root->children){
            res = max(res, maxDepth(node));
        }
        return res + 1;
    }
};

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }
    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

class Solution {
public:
    int countNodes(TreeNode* root) {
        int res = 0;
        if(root == nullptr) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int currentSize = q.size();
            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res += currentSize;
        } 
        return res;
    }
};

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

// 版本一
class Solution {
private:
    int getNodesNum(TreeNode* cur) {
        if (cur == 0) return 0;
        int leftNum = getNodesNum(cur->left);      // 左
        int rightNum = getNodesNum(cur->right);    // 右
        int treeNum = leftNum + rightNum + 1;      // 中
        return treeNum;
    }
public:
    int countNodes(TreeNode* root) {
        return getNodesNum(root);
    }
};

class Solution {
public:
    //求对应结点的深度，就是它的高度
/*
    int getDepth(TreeNode* cur) {
        int res = 0;
        if (cur == nullptr) return res;
        queue<TreeNode*> q;
        q.push(cur);
        while (!q.empty()) {
            res++;
            int currentSize = q.size();
            for (int i = 1; i <= currentSize; i++) {
                auto node = q.front();
                q.pop();
                if (node->right) q.push(node->right);  // 右
                if (node->left) q.push(node->left);    // 左
            }
        }
        return res;
    }
*/
    int getDepth(TreeNode* root){
        if(root == nullptr) return 0;
        return 1 + max(getDepth(root->left), getDepth(root->right));
    }
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            auto node = q.front();                       
            q.pop();
            if (abs(getDepth(node->left) - getDepth(node->right)) > 1) {
                return false;
            }
            if (node->right) q.push(node->right);          
            if (node->left) q.push(node->left);             
        }
        return true;
    }
};

class Solution {
public:
    int getDepth(TreeNode* root){
        if(root == nullptr) return 0;
        return 1 + max(getDepth(root->left), getDepth(root->right));
    }
    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return true;
        return abs(getDepth(root->left) - getDepth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度，如果不是二叉搜索树了则返回-1
    int getHeight(TreeNode* node) {
        if (node == nullptr)  return 0;
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(root == nullptr) return res;
        queue<TreeNode*> q;
        q.push(root);
        queue<string> p;
        p.push(to_string(root->val));
        while(!q.empty()){
            auto node = q.front();
            q.pop();
            string path = p.front();
            p.pop();
            if(node->left == nullptr && node->right == nullptr){ //遇到叶子结点
                res.push_back(path);
            }
            if(node->left){
                q.push(node->left);
                p.push(path + "->" + to_string(node->left->val));
            }
            if(node->right){
                q.push(node->right);
                p.push(path + "->" + to_string(node->right->val));
            }
        }
        return res;
    }
};

class Solution {
public:
  void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {  //1.确定递归函数的参数和返回值
    path.push_back(cur->val);
    // 这才到了叶子节点
    if (cur->left == NULL && cur->right == NULL) {   //2.确定终止条件
      string sPath;
      for (int i = 0; i < path.size(); i++) {
        sPath += to_string(path[i]);
        if(i != path.size() - 1)  sPath += "->";
      }
      result.push_back(sPath);
      return;
    }
        //3.确定单层递归逻辑
    if (cur->left) {
      traversal(cur->left, path, result);  //回溯和递归是一一对应的，有一个递归，就要有一个回溯
      path.pop_back(); // 回溯
    }
    if (cur->right) {
      traversal(cur->right, path, result);
      path.pop_back(); // 回溯
    }
  }
  vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> result;
    vector<int> path;
    if (root == NULL) return result;
    traversal(root, path, result);
    return result;
  }
};

class Solution {
public:
    void traversal(TreeNode* cur, string path, vector<string>& result) { //回溯体现在string不是引用类型
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left)   traversal(cur->left, path + "->", result); // 左
        if (cur->right)  traversal(cur->right, path + "->", result); // 右
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int res = 0;
        if(root == nullptr) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int currentSize = q.size();
            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();
                if(node->left) {
                    if(node->left->left == nullptr && node->left->right == nullptr){
                        res += node->left->val;
                    }
                    else{
                        q.push(node->left);
                    }
                }
                if(node->right) q.push(node->right);
            }
        }
        return res;
    }
};

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr) return 0;
        int leftValue = sumOfLeftLeaves(root->left);
        int rightValue = sumOfLeftLeaves(root->right); 
        int midValue = 0;
        if(root->left && root->left->left == nullptr && root->left->right == nullptr){
            midValue = root->left->val;
        }
        return midValue + leftValue + rightValue;
    }
};

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        vector<vector<int>> v;
        if(root == nullptr) return 0;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int currentSize = q.size();
            v.push_back(vector<int> ());
            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();
                v.back().push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);    
            }
        }
        return v.back()[0];
    }
};

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        //vector<vector<int>> v;
        if(root == nullptr) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int res = 0;
        while(!q.empty()){
            int currentSize = q.size();
            //v.push_back(vector<int> ());
            res = q.front()->val;   //记录每一层的第一个元素
            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();
                //v.back().push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);    
            }
        }
        return res;
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        queue<pair<TreeNode*, int>> q;
        q.push(make_pair(root, root->val));
        while (!q.empty()) {
            pair<TreeNode*, int> node = q.front();
            q.pop();  //两个容器   删除的差距
            if (!node.first->left && !node.first->right && node.second == targetSum) return true;
            if (node.first->left) q.push(make_pair(node.first->left, node.second + node.first->left->val));
            if (node.first->right) q.push(make_pair(node.first->right, node.second + node.first->right->val));
        }
        return false;
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode *root, int targetSum) {   //1.确定递归函数的参数和返回值
        if (root == nullptr)   return false;     //2.确定终止条件
        if (root->left == nullptr && root->right == nullptr) {   //3.确定单层递归逻辑
            return targetSum == root->val;
        }
        return hasPathSum(root->left, targetSum - root->val) ||
               hasPathSum(root->right, targetSum - root->val);
    }
};

class Solution {
public:
    vector<vector<int>> res;
    unordered_map<TreeNode*, TreeNode*> parent;  //第二参数为该节点的父结点
    void getPath(TreeNode* node){  //一路往父节点回溯，合成一个vector路径
        vector<int> temp;
        while(node != nullptr){
            temp.push_back(node->val);
            node = parent[node];
        }
        reverse(temp.begin(), temp.end());  //因为是反的
        res.push_back(temp);                    //添加到res里面
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root == nullptr)  return res;  //排除空树情况
        queue<TreeNode*> q;
        q.push(root);
    queue<int> qValue;
        qValue.push(root->val);
        while(!q.empty()){
            auto node = q.front();
            q.pop();
            int value = qValue.front();
            qValue.pop();
            //到叶子结点  且刚好==target
            if(node->left == nullptr && node->right == nullptr && value == targetSum)   getPath(node);   
            if(node->left){
                parent[node->left] = node;
                q.push(node->left);
                qValue.push(value + node->left->val);
            }     
            if(node->right){
                parent[node->right] = node;
                q.push(node->right);
                qValue.push(value + node->right->val);
            }
        }
        return res;
    }
};

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

class Solution{
public:
    vector<vector<int>> res;
    vector<int> path;
    void traversal(TreeNode* node, int count){
      //找到目标
        if(node->left == nullptr && node->right == nullptr && count == 0){
            res.push_back(path);
            return;
        }   
        if(node->left == nullptr && node->right == nullptr)  return;
        if(node->left){
            path.push_back(node->left->val);
            count -= node->left->val;
            traversal(node->left, count);
            count += node->left->val;  //回溯
            path.pop_back();           //回溯
        }
        if(node->right){
            path.push_back(node->right->val);
            count -= node->right->val;
            traversal(node->right, count);
            count += node->right->val;  //回溯
            path.pop_back();            //回溯
        }
        return;
    }
    vector<vector<int>> pathSum(TreeNode* root, int sum){
        if(root == nullptr) return res;
        path.push_back(root->val);  //把根结点放入路径
        traversal(root, sum - root->val);
        return res;
    }
};

class Solution {
public:
    TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;  //in和pos的size都一样，随意
        // 后序遍历数组最后一个元素，就是当前的中间节点
        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;
        }
        // 切割中序数组
        // 左闭右开区间：[0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        // [delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
        // postorder 舍弃末尾元素
        postorder.resize(postorder.size() - 1);
        // 切割后序数组
        // 依然左闭右开，注意这里使用了左中序数组大小作为切割点
        // [0, leftInorder.size)
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        // [leftInorder.size(), end)
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
        //递归套娃
        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0)  return NULL;
        return traversal(inorder, postorder);
    }
};

class Solution {
public:
    // 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
    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 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;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0) return NULL;
        // 左闭右开的原则
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
}; 

class Solution {
public:
    TreeNode* traversal(vector<int>& preorder, vector<int>& inorder){
        if(preorder.size() == 0)  return NULL;
        //前序遍历的第一个元素就是当前中间结点
        int rootValue = preorder[0];
        TreeNode* root = new TreeNode(rootValue);
        //叶子结点
        if(preorder.size() == 1) return root;
        //找到中序遍历的切割点
        int delimiterIndex;
        for(delimiterIndex = 0; delimiterIndex < inorder.size(); ++delimiterIndex){
            if(inorder[delimiterIndex] == rootValue)  break;
        }
        //切割中序数组
        //左闭右开区间： [0, delimiterInedx)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        //[delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());
        //切割前序数组
        //[1, leftInorder.size)
        vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size());
        //[leftInorder.size, end)
        vector<int> rightPreorder(preorder.begin() + 1 + leftInorder.size(), preorder.end());
        root->left = traversal(leftPreorder, leftInorder);
        root->right = traversal(rightPreorder, rightInorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(inorder.size() == 0)  return NULL;
        return traversal(preorder, inorder);
    }
};

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if (nums.size() == 1) {      //3. 确定终止条件
            node->val = nums[0];
            return node;
        }
        // 1. 找到数组中最大的值和对应的下标
        int maxValue = 0;
        int maxValueIndex = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        node->val = maxValue;   //2. 确定中间结点
        // 最大值所在的下标左区间 构造左子树
        if (maxValueIndex > 0) {
            vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
            node->left = constructMaximumBinaryTree(newVec);
        }
        // 最大值所在的下标右区间 构造右子树
        if (maxValueIndex < (nums.size() - 1)) {
            vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};

class Solution {
public:
    // 在左闭右开区间[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;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
};