代码随想录打卡第十六天

代码随想录–二叉树部分

day16 二叉树第四天

文章目录

• 代码随想录--二叉树部分
• 一、力扣513--找树左下角的值
• 二、力扣112--路径总和
• 三、力扣106--从中序与后序遍历序列构造二叉树

  ---

  一、力扣513–找树左下角的值

  代码随想录题目链接：代码随想录

  给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

  假设二叉树中至少有一个节点。

  层序遍历秒了，没什么好讲的

  代码如下：

  class Solution {
  public:
      int findBottomLeftValue(TreeNode* root) {
          queue que;
          que.push(root);
          vector temp;
          while(!que.empty())
          {
              int length = que.size();
              for(int i = 0; i left) que.push(curr->left);
                  if(curr->right) que.push(curr->right);
                  if(i == 0) temp.push_back(curr->val);
              }
          }
          return temp[temp.size()-1];
      }
  };
  

  递归法的话，需要回溯，递归到最底层后再判断是否为最左边的节点。

  class Solution {
  public:
      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) {
              depth++;
              traversal(root->left, depth);
              depth--; 
          }
          if (root->right) {
              depth++;
              traversal(root->right, depth);
              depth--; 
          }
          return;
      }
      int findBottomLeftValue(TreeNode* root) {
          traversal(root, 0);
          return result;
      }
  };
  

  二、力扣112–路径总和

  代码随想录题目链接：代码随想录

  给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

  叶子节点 是指没有子节点的节点。

  可以类似二叉树的所有路径方式写一个回溯，然后计算每个path的总和

  代码如下：

  class Solution {
  public:
      bool traversal(TreeNode * curr, vector & path, int targetSum)
      {
          if(!curr->left && !curr->right)
          {
              int sum = 0;
              for(auto ele : path)
              {
                  sum += ele;
              }
              if(sum + curr->val == targetSum) return true;
              else return false;
          }
          if(curr->left)
          {
              path.push_back(curr->val);
              if(traversal(curr->left, path, targetSum)) return true;
              path.pop_back();
          }
          if(curr->right)
          {
              path.push_back(curr->val);
              if(traversal(curr->right, path, targetSum)) return true;
              path.pop_back();
          }
          return false;
      }
      bool hasPathSum(TreeNode* root, int targetSum) {
          vector path;
          if(!root) return false;
          return traversal(root, path, targetSum);
      }
  };
  

  附加题：力扣113–路径总和Ⅱ

  遍历所有路径时加个判断即可，如果通过就把当前的path加入result，注意要把当前节点的val加入path后再进result，进完需要把当前节点的val再pop出来，不然会影响回溯

  class Solution {
  public:
      void traversal(TreeNode * curr, vector path, int targetSum, vector &result)
      {
          if(!curr->left && !curr->right)
          {
              int sum = 0;
              for(auto ele : path) sum += ele;
              sum += curr->val;
              if(sum == targetSum) 
              {
                  path.push_back(curr->val);
                  result.push_back(path);
                  path.pop_back();
              }
          }
          if(curr->left)
          {
              path.push_back(curr->val);
              traversal(curr->left, path, targetSum, result);
              path.pop_back();
          }
          if(curr->right)
          {
              path.push_back(curr->val);
              traversal(curr->right, path, targetSum, result);
              path.pop_back();
          }
          
      }
      vector pathSum(TreeNode* root, int targetSum) {
          if(!root) return {};
          vector path;
          vector result;
          traversal(root, path, targetSum, result);
          return result;
      }
  };
  

  三、力扣106–从中序与后序遍历序列构造二叉树

  代码随想录题目链接：代码随想录

  给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

  如何通过中序和后序构建二叉树参考链接讲解

  这个题的递归也比较清晰，取后序的最后一位，用其对中序分割，再返回来分割后序，从而能够递归构建左右子树

  难点在于怎么分割

  代码如下：

  class Solution {
  public:
      TreeNode* traversal(vector inorder, vector postorder)
      {
          if(!inorder.empty() && !postorder.empty())
          {
              TreeNode * curr = new TreeNode(postorder[postorder.size()-1]);
              if(postorder.size() == 1) return curr;
              int delimiterIndex;
              for (delimiterIndex = 0; delimiterIndex left = traversal(leftInorder, leftPostorder);
              curr->right = traversal(rightInorder, rightPostorder);
              return curr;   
          }
          return nullptr;
      }
      TreeNode* buildTree(vector& inorder, vector& postorder) {
          if(inorder.empty() || postorder.empty()) return nullptr;  
          // this can be delete cause traversal() can deal with it
          return traversal(inorder, postorder);
      }
  };
  

  想起来了vector分割可以用

  vector X(vectorB.begin(), vectorB.end());
  

  来创建一个指定的vector，不需要自己去遍历插入

  附加题：力扣105–从前序与中序遍历序列构造二叉树

  不同于106，本题要用前序遍历的首节点去分割，剩下思路一样

  代码如下：

  class Solution {
  public:
      TreeNode * traversal(vector& preorder, vector& inorder)
      {
          if(preorder.empty() || inorder.empty()) return nullptr;
          TreeNode * curr = new TreeNode(preorder[0]);
          if(preorder.size() == 1) return curr;
          int diff = 0;
          for(diff = 0; diff left = traversal(leftPreorder, leftInorder);
          curr->right = traversal(rightPreorder, rightInorder);
          return curr;
      }
      TreeNode* buildTree(vector& preorder, vector& inorder) {
          return traversal(preorder, inorder);
      }
  };