513.找树左下角的值

题目描述：给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。

我的解法（迭代法）

思路

用层序遍历，每一层只保存最左边的值，每遍历一层再更新。

• 层序遍历
• 我的写法
  个人感觉是不能通过的，但是还是跑通了？？
  下面的写法是每一层从右往左遍历，所以遍历到最后一个的时候刚好是最左边的元素

class Solution {
public:
  int findBottomLeftValue(TreeNode *root) {
    queue<TreeNode *> que;
    if (root) {
      que.push(root);
    }
    int res;
    while (!que.empty()) {
      int size = que.size();
      while (size--) {
        TreeNode *cur = que.front();
        que.pop();
        res = cur->val;
        if (cur->right) {
          que.push(cur->right);
        }
        if (cur->left) {
          que.push(cur->left);
        }
      }
    }
    return res;
  }
};

• 题解写法

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int result = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == 0) result = node->val; // 记录最后一行第一个元素
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

递归法

还是采用回溯的思想

class Solution {
public:
  int maxDepth = INT_MIN;
  int res;
  void getDepth(TreeNode *cur, int depth) {
    if (!cur->left && !cur->right) {
      if (depth > maxDepth) {
        maxDepth = depth;//更新最大深度
        res = cur->val;
      }
      return;
    }

    if (cur->left) {
      depth++;
      getDepth(cur->left, depth);
      depth--;//回溯
    }
    if (cur->right) {
      depth++;
      getDepth(cur->right, depth);
      depth--;
    }
    return;
  }
  
  int findBottomLeftValue(TreeNode *root) {
    getDepth(root, 0);
    return res;
  }
};

• 精简代码

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) {
            traversal(root->left, depth + 1); // 隐藏着回溯
        }
        if (root->right) {
            traversal(root->right, depth + 1); // 隐藏着回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

相信很多同学都会疑惑，递归函数什么时候要有返回值，什么时候没有返回值，特别是有的时候递归函数返回类型为bool类型。

递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

• 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
• 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。
• 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。

112.路径总和

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

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

思路

尝试使用回溯法来解。

递归法

关键思路

在于左右节点的回溯处理，先往下加，然后将下面加的节点放入递归中，如果找到了正确的，就直接return true，如果不正确，出来之后进行回溯操作，撤销刚刚加的。

• 我的解法（不是一次写出，参考了题解）

class Solution {
public:
  int sum;
  bool getPath(TreeNode *node, int target) {

    if ((!node->left && !node->right) && sum == target) {
      return true;
    }
    if (!node->left && !node->right) {
      return false;
    }

    if (node->left) {
      sum += node->left->val;
      if (getPath(node->left, target)) {//如果左孩子拿到了正确结果就继续向上返回
        return true;
      }
      sum -= node->left->val;
    }
    if (node->right) {
      sum += node->right->val;
      if (getPath(node->right, target)) {
        return true;
      }
      sum -= node->right->val;
    }
    
    return false;
  }
  bool hasPathSum(TreeNode *root, int targetSum) {
    if (root) {
      sum += root->val;
      return getPath(root, targetSum);
    }
    return false;
  }
};

• 题解

class Solution {
private:
    bool traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回

        if (cur->left) { // 左
            count -= cur->left->val; // 递归，处理节点;
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯，撤销处理结果
        }
        if (cur->right) { // 右
            count -= cur->right->val; // 递归，处理节点;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯，撤销处理结果
        }
        return false;
    }

public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;
        return traversal(root, sum - root->val);
    }
};

• 精简版

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right && sum == root->val) {
            return true;
        }
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

迭代法

113.路径总和 II

题目描述：给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

路径总和ii要遍历整个树，找到所有路径，所以递归函数不要返回值！

• 我的解法

class Solution {
public:
  vector<vector<int>> res;
  vector<int> path;
  int sum;

  void getPath(TreeNode *cur, int target) {
    if ((!cur->left && !cur->right) && sum == target) {
      res.push_back(path);
      return;
    }

    if (!cur->left && !cur->right) {
      return;
    }

    if (cur->left) {
      path.push_back(cur->left->val);
      sum += cur->left->val;
      getPath(cur->left, target);
      sum -= cur->left->val;
      path.pop_back();
    }

    if (cur->right) {
      path.push_back(cur->right->val);
      sum += cur->right->val;
      getPath(cur->right, target);
      sum -= cur->right->val;
      path.pop_back();
    }

    return;
  }

  vector<vector<int>> pathSum(TreeNode *root, int targetSum) {
    res.clear();
    path.clear();
    if (!root) {
      return res;
    }
    path.push_back(root->val);
    sum+=root->val;//先把根节点的值加上
    getPath(root, targetSum);
    return res;
  }
};

• 题解

class Solution {
public:
  vector<vector<int>> res;
  vector<int> path;
  int sum;

  void getPath(TreeNode *cur, int target) {
    if ((!cur->left && !cur->right) && sum == target) {
      res.push_back(path);
      return;
    }

    if (!cur->left && !cur->right) {
      return;
    }

    if (cur->left) {
      path.push_back(cur->left->val);
      sum += cur->left->val;
      getPath(cur->left, target);
      sum -= cur->left->val;
      path.pop_back();
    }

    if (cur->right) {
      path.push_back(cur->right->val);
      sum += cur->right->val;
      getPath(cur->right, target);
      sum -= cur->right->val;
      path.pop_back();
    }

    return;
  }

  vector<vector<int>> pathSum(TreeNode *root, int targetSum) {
    res.clear();
    path.clear();
    if (!root) {
      return res;
    }
    path.push_back(root->val);
    sum+=root->val;
    getPath(root, targetSum);
    return res;
  }
};

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

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

注意: 你可以假设树中没有重复的元素。

思路

根据后序数组找到根节点，在中序数组中利用根节点划分出左右子树的数组。再对左右子树进行相同的处理。

注意数组左右区间处理逻辑

• 能直接体现思路的版本

class Solution {
private:
    TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;

        // 后序遍历数组最后一个元素，就是当前的中间节点
        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;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

• 性能优化版，减少了每次递归要重新创建vector的过程

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