LeetCode刷题记录（二叉树篇）

LeetCode刷题记录（二叉树篇），个人向。
这部分涉及频繁的指针操作，因此专精C++来做题。

[144]、[145]、[94]

题目描述就不放了，就是二叉树的前中后序遍历。考察最基本的数据结构了解程度，无难度。这里放几种不同的实现方式。

递归遍历

前序遍历。

class Solution {
 public:
  void traverse(TreeNode* cur, vector<int>& res) {
    if (!cur) {
      return;
    }
    res.push_back(cur->val);
    traverse(cur->left, res);
    traverse(cur->right, res);
  }

  vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    traverse(root, res);
    return res;
  }
};

后序遍历。

class Solution {
 public:
  void traverse(TreeNode* cur, vector<int>& res) {
    if (!cur) {
      return;
    }
    traverse(cur->left, res);
    traverse(cur->right, res);
    res.push_back(cur->val);
  }

  vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    traverse(root, res);
    return res;
  }
};

中序遍历。

class Solution {
 public:
  void traverse(TreeNode* cur, vector<int>& res) {
    if (!cur) {
      return;
    }
    traverse(cur->left, res);
    res.push_back(cur->val);
    traverse(cur->right, res);
  }

  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    traverse(root, res);
    return res;
  }
};

三种遍历的递归写法代码基本一样，改下traverse里面顺序即可。

迭代遍历

前序遍历。使用栈来存放节点。
注意要先入右节点再入左节点，这样左节点会先出栈，才符合前序遍历顺序。

class Solution {
 public:
  vector<int> preorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    if (!root) return result;
    st.push(root);
    while (!st.empty()) {
      TreeNode* cur = st.top();
      st.pop();
      result.push_back(cur->val);
      if (cur->right) st.push(cur->right);
      if (cur->left) st.push(cur->left);
    }
    return result;
  }
};

后序遍历。和前序遍历类似。
为了满足后续遍历的顺序，我们可以交换左右节点入栈的顺序（即先入左节点再入右节点），最后再把结果反转一下顺序。
这样一来，原本前序遍历为中左右，交换入栈顺序变成中右左，结果反转后变成左右中。

class Solution {
 public:
  vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    if (!root) return result;
    st.push(root);
    while (!st.empty()) {
      TreeNode* cur = st.top();
      st.pop();
      result.push_back(cur->val);
      if (cur->left) st.push(cur->left);
      if (cur->right) st.push(cur->right);
    }
    reverse(result.begin(), result.end());
    return result;
  }
};

中序遍历会更麻烦些。在前序遍历中，当前节点访问过就可以丢掉了，但是在中序遍历中我们需要把当前节点先入栈存起来，并尽量的先往左遍历，直到遍历到头再尝试弹栈并往右移动。
注意在后序遍历中，我们通过结果反转的方式巧妙规避了这些问题，但中序遍历就不行了。
在写代码时请注意在空节点是否入栈上达成统一意见（以防止写出bug），本人给出的是空节点不入栈的写法。

class Solution {
 public:
  vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
      if (cur) {
        st.push(cur);
        cur = cur->left;
      } else {
        cur = st.top();
        st.pop();
        result.push_back(cur->val);
        cur = cur->right;
      }
    }
    return result;
  }
};

统一迭代法

在前面的迭代方法中，前中后序的写法都不一样，没有做到像递归遍历一样的稍微改下代码顺序即可。因此，对于非递归的方法，也有统一的写法，可做到稍微改下代码顺序即可更改遍历顺序。
统一迭代法的关键是，利用了空指针来做标记，即访问到的节点后会再跟一个空指针入栈，弹栈时遇到空指针才把后面的节点进行处理（加入结果集）。即一个节点实际上会入栈出栈两次，第一次（入栈不带空指针）代表访问到（仅仅是路过），第二次（入栈后带空指针）才代表要处理该节点。
于是，我们可以很容易得到三种遍历的写法。
前序遍历。

class Solution {
 public:
  vector<int> preorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    if (root) st.push(root);
    while (!st.empty()) {
      TreeNode* cur = st.top();
      st.pop();
      if (cur) {
        if (cur->right) st.push(cur->right);
        if (cur->left) st.push(cur->left);
        st.push(cur);
        st.push(nullptr);
      } else {
        result.push_back(st.top()->val);
        st.pop();
      }
    }
    return result;
  }
};

后序遍历。

class Solution {
 public:
  vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    if (root) st.push(root);
    while (!st.empty()) {
      TreeNode* cur = st.top();
      st.pop();
      if (cur) {
        st.push(cur);
        st.push(nullptr);
        if (cur->right) st.push(cur->right);
        if (cur->left) st.push(cur->left);
      } else {
        result.push_back(st.top()->val);
        st.pop();
      }
    }
    return result;
  }
};

中序遍历。

class Solution {
 public:
  vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    if (root) st.push(root);
    while (!st.empty()) {
      TreeNode* cur = st.top();
      st.pop();
      if (cur) {
        if (cur->right) st.push(cur->right);
        st.push(cur);
        st.push(nullptr);
        if (cur->left) st.push(cur->left);
      } else {
        result.push_back(st.top()->val);
        st.pop();
      }
    }
    return result;
  }
};

[102] Binary Tree Level Order Traversal

题目描述。
二叉树的层序遍历，也属于数据结构的基本操作。
层序遍历其实就相当于图论的广度优先搜索。只不过，这道题的返回类型是二维vector，即要求把每一层的节点单独作为一个vector<int>分出来，因此我们在内部嵌套一个循环来专门处理某一层的节点。否则，我们只保留最外层的while循环即可（不关心每层的节点从什么地方开始和结束，即退化到广度优先搜索）。

class Solution {
 public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) {
      return result;
    }

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
      int level_width = q.size();
      vector<int> cur_level;
      while (level_width-- > 0) {
        TreeNode* cur = q.front();
        q.pop();
        cur_level.push_back(cur->val);
        if (cur->left) {
          q.push(cur->left);
        }
        if (cur->right) {
          q.push(cur->right);
        }
      }
      result.push_back(cur_level);
    }

    return result;
  }
};

[226] Invert Binary Tree

题目描述。
之前讲了很多种遍历方法，随便选一种用，遍历的同时交换当前节点的左右儿子即可。这里我选用的是递归前序遍历。
需要注意的是，如果选用的是递归中序遍历，两次traversal都要对cur->left进行，因为左右儿子在中间被交换了。

class Solution {
 public:
  void traversal(TreeNode* cur) {
    if (!cur) {
      return;
    }
    TreeNode* tmp = cur->left;
    cur->left = cur->right;
    cur->right = tmp;
    traversal(cur->left);
    traversal(cur->right);
  }
  TreeNode* invertTree(TreeNode* root) {
    traversal(root);
    return root;
  }
};

[101] Symmetric Tree

题目描述。
同时遍历根节点的左右子树，遍历的同时进行比较即可。注意左子树的left和右子树的right比较，左子树的right和右子树的left比较。
这里使用的是递归的写法。实际上，用队列或者栈等等也可以有不递归的写法（迭代法）。具体来说，就是把left_cur->left, right_cur->right放进容器中，left_cur->right, right_cur->left放进容器中，然后成对从容器中取元素，进行判断即可。具体可见这篇solution。

class Solution {
 public:
  bool traversal(TreeNode* left_cur, TreeNode* right_cur) {
    if (!left_cur || !right_cur) {
      if (left_cur == right_cur) {
        return true;
      } else {
        return false;
      }
    }

    if (left_cur->val != right_cur->val) {
      return false;
    }

    return traversal(left_cur->left, right_cur->right) &&
           traversal(left_cur->right, right_cur->left);
  }

  bool isSymmetric(TreeNode* root) {
    if (!root) {
      return true;
    }

    return traversal(root->left, root->right);
  }
};

[104] Maximum Depth of Binary Tree

题目描述。
比较闲就顺手写了非递归层序和递归前序的两种写法。事实上这道题写法应该很多，要做的就只是在遍历的同时记录一下深度即可。在这里的话，我选择在非递归层序遍历时用空指针记录一层的结束，然后直接++max_depth；在递归前序遍历中我选择记录cur_level并看条件更新max_level。

class Solution {
 public:
  int maxDepthLevel(TreeNode* root) {
    if (!root) {
      return 0;
    }

    int max_depth = 0;
    queue<TreeNode*> q;
    q.push(root);
    q.push(nullptr);
    while (!q.empty()) {
      TreeNode* cur = q.front();
      q.pop();
      if (!cur) {
        ++max_depth;
        if (!q.empty()) {
          // Not the last level
          q.push(nullptr);
        }
      } else {
        if (cur->left) {
          q.push(cur->left);
        }
        if (cur->right) {
          q.push(cur->right);
        }
      }
    }
    return max_depth;
  }

  void traversal(TreeNode* cur, int cur_level, int& max_level) {
    if (!cur) {
      return;
    }
    cur_level += 1;
    max_level = cur_level > max_level ? cur_level : max_level;
    traversal(cur->left, cur_level, max_level);
    traversal(cur->right, cur_level, max_level);
  }

  int maxDepth(TreeNode* root) {
    int max_level = 0;
    traversal(root, 0, max_level);
    return max_level;
  }
};

[111] Minimum Depth of Binary Tree

题目描述。
在104的基础上稍加改动即可。在遍历的时候，遇到当前节点的左右儿子都是空指针，说明遇到叶子节点，就可以尝试更新min_level了。

class Solution {
 public:
  void traversal(TreeNode* cur, int cur_level, int& min_level) {
    if (!cur) {
      return;
    }
    if (!cur->left && !cur->right) {
      min_level = cur_level < min_level ? cur_level : min_level;
    }
    traversal(cur->left, cur_level + 1, min_level);
    traversal(cur->right, cur_level + 1, min_level);
  }

  int minDepth(TreeNode* root) {
    if (!root) {
      return 0;
    }

    int min_level = __INT_MAX__;
    traversal(root, 1, min_level);
    return min_level;
  }
};

[222] Count Complete Tree Nodes

题目描述。
往下遍历的过程中一定会遇到满二叉树，对于满二叉树可以用 $2^h - 1$ 的公式快速计算数量。可以用向左遍历和向右遍历的深度是否一致来判断当前子树是否为满二叉树，如不是，则往左右子树继续递归（后序遍历）即可。

class Solution {
 public:
  int countNodes(TreeNode* root) {
    if (!root) {
      return 0;
    }

    TreeNode* left = root->left;
    TreeNode* right = root->right;
    int left_depth = 0;
    int right_depth = 0;
    while (left) {
      left = left->left;
      left_depth += 1;
    }
    while (right) {
      right = right->right;
      right_depth += 1;
    }
    if (left_depth == right_depth) {
      return (2 << left_depth) - 1;
    }

    return countNodes(root->left) + countNodes(root->right) + 1;
  }
};

[110] Balanced Binary Tree

题目描述。
使用后序遍历获取节点高度，同时使用-1来表示子树不平衡。在遍历的同时比较左右子树的高度，如果高度差值绝对值大于1则返回-1即可。

class Solution {
 public:
  int getHeight(TreeNode* cur) {
    if (!cur) {
      return 0;
    }

    int left_height = getHeight(cur->left);
    if (left_height < 0) {
      return -1;
    }
    int right_height = getHeight(cur->right);
    if (right_height < 0) {
      return -1;
    }

    if (abs(left_height - right_height) > 1) {
      return -1;
    }

    return max(left_height, right_height) + 1;
  }

  bool isBalanced(TreeNode* root) { return getHeight(root) >= 0; }
};

[257] Binary Tree Paths

前序遍历的同时，记录当前走过的路径（cur_path），在遇到叶子节点时再存入all_path即可。由于题目要求字符串格式的路径，所以增加了pathToString用来把vector<TreeNode*>转为string。

class Solution {
 public:
  string pathToString(vector<TreeNode*> path) {
    string s;
    for (TreeNode* node : path) {
      s.append(to_string(node->val));
      s.append("->");
    }
    s.erase(s.end() - 2, s.end());
    return s;
  }

  void traverse(TreeNode* cur, vector<string>& all_paths,
                vector<TreeNode*> cur_path) {
    cur_path.push_back(cur);
    if (!cur->left && !cur->right) {
      all_paths.push_back(pathToString(cur_path));
      return;
    }
    if (cur->left) {
      traverse(cur->left, all_paths, cur_path);
    }
    if (cur->right) {
      traverse(cur->right, all_paths, cur_path);
    }
  }

  vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> result;
    if (!root) {
      return result;
    }
    vector<TreeNode*> cur_path;
    traverse(root, result, cur_path);
    return result;
  }
};

[404] Sum of Left Leaves

题目描述。
无什么难度的题目。遍历的同时使用一个参数left_falg来记录当前节点是否是其父节点的左儿子即可。

class Solution {
 public:
  int traverse(TreeNode* cur, bool left_flag) {
    if (!cur->left && !cur->right) {
      return left_flag ? cur->val : 0;
    }

    int sum = 0;
    if (cur->left) {
      sum += traverse(cur->left, true);
    }
    if (cur->right) {
      sum += traverse(cur->right, false);
    }
    return sum;
  }

  int sumOfLeftLeaves(TreeNode* root) {
    if (!root) {
      return 0;
    }
    return traverse(root, false);
  }
};

[513] Find Bottom Left Tree Value

题目描述。
很容易想到使用层序遍历，记录最后一层最左边的节点即可。这里也写了一个递归的写法，在遍历的同时记录当前深度，由于是前序遍历（先左后右），所以在第一次到达新的深度时记录节点即可。

class Solution {
 public:
  void traversal(TreeNode* cur, int cur_level, int& left_most_val,
                 int& most_level) {
    if (cur_level > most_level) {
      left_most_val = cur->val;
      most_level = cur_level;
    }
    if (cur->left) {
      traversal(cur->left, cur_level + 1, left_most_val, most_level);
    }
    if (cur->right) {
      traversal(cur->right, cur_level + 1, left_most_val, most_level);
    }
  }

  int findBottomLeftValueRecursive(TreeNode* root) {
    int left_most_val = 0;
    int most_level = 0;
    if (!root) {
      return left_most_val;
    }

    traversal(root, 1, left_most_val, most_level);

    return left_most_val;
  }

  int findBottomLeftValue(TreeNode* root) {
    int left_most_val = 0;
    if (!root) {
      return left_most_val;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
      int width = q.size();
      for (int i = 0; i < width; ++i) {
        TreeNode* cur = q.front();
        q.pop();
        if (i == 0) {
          left_most_val = cur->val;
        }
        if (cur->left) {
          q.push(cur->left);
        }
        if (cur->right) {
          q.push(cur->right);
        }
      }
    }
    return left_most_val;
  }
};

[112] Path Sum

题目描述。
在遍历的同时记录一下当前cur_sum，在遇到叶子节点时再判断一下是否等于target即可。
也可以换成把一个参数递减一直减到0而不是求和然后判断是否相等，这样代码可以更简洁，可参考这篇。
也可以用迭代的方式，使用pair<TreeNode*, int>来存储节点指针和对应的路径数值即可。

class Solution {
 public:
  bool traversal(TreeNode* cur, int cur_sum, int target) {
    cur_sum += cur->val;
    bool result = false;
    if (!cur->left && !cur->right && cur_sum == target) {
      return true;
    }
    if (cur->left) {
      result |= traversal(cur->left, cur_sum, target);
    }
    if (!result && cur->right) {
      result |= traversal(cur->right, cur_sum, target);
    }
    return result;
  }
  bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) {
      return false;
    }
    return traversal(root, 0, targetSum);
  }
};

[106] Construct Binary Tree from Inorder and Postorder Traversal

题目描述。
后序遍历的最后一个一定是根节点。利用这个特性，我们使用该节点在中序遍历中划分左右子树，然后再依次在左右子树中递归即可。

class Solution {
 public:
  TreeNode* traversal(vector<int>& inorder, vector<int>& postorder,
                      int inorder_begin, int inorder_end, int postorder_begin,
                      int postorder_end) {
    if (postorder_begin == postorder_end) {
      return nullptr;
    }
    int cur_val = postorder[postorder_end - 1];
    TreeNode* cur = new TreeNode(cur_val);
    if (postorder_begin + 1 < postorder_end) {  // early stop
      for (int i = inorder_begin; i < inorder_end; ++i) {
        if (inorder[i] == cur_val) {
          cur->left =
              traversal(inorder, postorder, inorder_begin, i, postorder_begin,
                        postorder_begin + i - inorder_begin);
          cur->right =
              traversal(inorder, postorder, i + 1, inorder_end,
                        postorder_begin + i - inorder_begin, postorder_end - 1);

          break;
        }
      }
    }

    return cur;
  }

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

[654] Maximum Binary Tree

题目描述。
递归的同时找一下当前index范围内的最大值作为当前TreeNode，然后递归找[left_index, max_index)和[max_index + 1, right_index)即可，没什么难度。

class Solution {
 public:
  TreeNode* traversal(vector<int>& nums, int left_index, int right_index) {
    if (right_index - left_index == 1) {
      return new TreeNode(nums[left_index]);
    }

    int max_index = left_index;
    int max_val = -1;
    for (int i = left_index; i < right_index; ++i) {
      if (nums[i] > max_val) {
        max_val = nums[i];
        max_index = i;
      }
    }
    TreeNode* cur = new TreeNode(max_val);
    if (max_index > left_index) {
      cur->left = traversal(nums, left_index, max_index);
    }
    if (right_index > max_index + 1) {
      cur->right = traversal(nums, max_index + 1, right_index);
    }
    return cur;
  }
  TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    return traversal(nums, 0, nums.size());
  }
};

[617] Merge Two Binary Trees

题目描述。
同时遍历两棵树即可，没什么难度。
这里复用了两棵树的节点。如果不想复用也可一路创建新节点即可。

class Solution {
 public:
  TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (!root1) return root2;
    if (!root2) return root1;

    TreeNode* cur = new TreeNode(root1->val + root2->val);
    cur->left = mergeTrees(root1->left, root2->left);
    cur->right = mergeTrees(root1->right, root2->right);
    return cur;
  }
};

[700] Search in a Binary Search Tree

题目描述。
二叉搜索树的最基本操作，无难度。

class Solution {
 public:
  TreeNode* searchBST(TreeNode* root, int val) {
    TreeNode* cur = root;
    while (cur) {
      if (cur->val == val) {
        return cur;
      }
      if (cur->val < val) {
        cur = cur->right;
      } else {
        cur = cur->left;
      }
    }
    return cur;
  }
};

[98] Validate Binary Search Tree

题目描述。
写了两种解法。一种是自己写的前序遍历，遍历过程传入left_bound和right_bound，把当前节点的左右儿子与当前节点和对应bound做比较，然后递归遍历其左右子树。
另一种解法是写完后看到的网上的解法，使用的是中序遍历，其核心是使用了二叉搜索树中序遍历输出的节点数值是有序序列的性质。通过中序遍历的这个性质，我们只需要记录一个pre即当前节点左边的节点（也可以只记录数值，但是要注意如果题目出现long long类型的最小值就没法初始化成更小了，所以记录节点更好），然后只比较当前节点的数值和这个pre的数值大小即可。

class Solution {
 public:
  bool traversal(TreeNode* cur, long long left_bound, long long right_bound) {
    if (!cur) {
      return true;
    }
    if (cur->left &&
        (cur->left->val >= cur->val || cur->left->val <= left_bound)) {
      return false;
    }
    if (cur->right &&
        (cur->right->val <= cur->val || cur->right->val >= right_bound)) {
      return false;
    }
    return traversal(cur->left, left_bound, cur->val) &&
           traversal(cur->right, cur->val, right_bound);
  }

  TreeNode* pre = nullptr;

  bool isValidBST(TreeNode* root) {
    // return traversal(root, -__LONG_LONG_MAX__ - 1, __LONG_LONG_MAX__);
    if (!root) {
      return true;
    }
    bool result = isValidBST(root->left);
    if (pre && root->val <= pre->val) {
      return false;
    } else {
      pre = root;
    }
    result &= isValidBST(root->right);
    return result;
  }
};

[530] Minimum Absolute Difference in BST

题目描述。
参照上一题，我们已经知道了二叉搜索树中序遍历输出的节点数值是有序序列。通过这个性质，我们只需在这个有序序列中计算当前节点和上一个节点的差值，然后记录最小值即可。

class Solution {
 public:
  TreeNode* pre = nullptr;
  int min_abs_diff = __INT_MAX__;
  int getMinimumDifference(TreeNode* root) {
    if (!root) {
      return false;
    }
    getMinimumDifference(root->left);
    if (pre && root->val - pre->val < min_abs_diff) {
      min_abs_diff = root->val - pre->val;
    }
    pre = root;
    getMinimumDifference(root->right);
    return min_abs_diff;
  }
};

[501] Find Mode in Binary Search Tree

题目描述。
和之前一样的思路，采用中序遍历。使用pre && cur->val != pre->val来判断是应该把cut_count置1还是加1。然后，对比cur_count与max_count，来对结果result进行更新。

class Solution {
 public:
  vector<int> result;
  TreeNode* pre = nullptr;
  int max_count = 0;
  int cur_count = 0;

  void traversal(TreeNode* cur) {
    if (!cur) {
      return;
    }

    traversal(cur->left);
    if (pre && cur->val != pre->val) {
      cur_count = 1;
    } else {
      cur_count += 1;
    }
    if (cur_count == max_count) {
      result.push_back(cur->val);
    } else if (cur_count > max_count) {
      result.clear();
      result.push_back(cur->val);
      max_count = cur_count;
    }
    pre = cur;
    traversal(cur->right);
  }

  vector<int> findMode(TreeNode* root) {
    if (!root) {
      return result;
    }
    traversal(root);
    return result;
  }
};

[236] Lowest Common Ancestor of a Binary Tree

题目描述。
一开始写了一个naive的写法：遍历树，在遍历的同时记录路径，以此分别找到到达p和q的路径，然后再把两个路径进行对比，找到路径出现不一致的地方，其最后一个一致的节点就是最近公共祖先了。但写完发现这种解法效率较低。
实际上我们没有必要记录路径。我们只需要在遍历的同时，遇到p和q就返回（否则遍历到底然后返回空指针）。使用后序遍历，我们可查看其左右子树是否遍历到了p或q，若是则当前节点就是最近公共祖先。若left和right有一个为空，则返回另一个即可（一是传递结果，二是p或q可能本身是公共祖先）。通过这种方式我们避免了路径的记录，大大提高了效率。

class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) {
      return nullptr;
    }
    if (root == p || root == q) {
      return root;
    }
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) {
      return root;
    }
    if (!left) {
      return right;
    }
    return left;
  }
};

[235] Lowest Common Ancestor of a Binary Search Tree

题目描述。
利用二叉搜索树有序的性质，直接遍历，找到值处于[p, q]（或[q, p]）区间的节点即可。

class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) {
      return nullptr;
    }
    if ((p->val <= root->val && q->val >= root->val) ||
        p->val >= root->val && q->val <= root->val) {
      return root;
    }
    if (p->val < root->val) {
      return lowestCommonAncestor(root->left, p, q);
    } else {
      return lowestCommonAncestor(root->right, p, q);
    }
  }
};

[701] Insert into a Binary Search Tree

题目描述。
一路查找，找到对应空指针的位置插入即可。

class Solution {
 public:
  TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) {
      return new TreeNode(val);
    }
    TreeNode* cur = root;
    while (true) {
      if (val > cur->val) {
        if (cur->right) {
          cur = cur->right;
        } else {
          cur->right = new TreeNode(val);
          break;
        }
      } else {
        if (cur->left) {
          cur = cur->left;
        } else {
          cur->left = new TreeNode(val);
          break;
        }
      }
    }
    return root;
  }
};

[450] Delete Node in a BST

题目描述。
二叉搜索树的基本操作之一，但是有一定难度。要删除一个节点，我们肯定要先找到这个节点。这里分成了几种情况。

该节点不存在。什么都不用干。
该节点只有左子树或右子树。把其左子树或右子树接到其父节点上即可（还要判断一下父节点是否存在以及该节点是其父节点的左孩子还是右孩子）。
该节点同时有左子树和右子树。可以找到其右子树的最左节点（也就是树里面值最接近该节点的比该节点大的节点）替换到该节点上。可以直接替换节点，但我这里写的是赋值的写法（cur->val = right->val;），然后再把这个原先的右子树最左（位置的）节点删掉。

把右子树最左节点挪过来的方法只是解法之一，也可以把cur->left直接接到其右子树最左节点的左边，可参考这篇solution。但是个人感觉这样会使树的深度加深，太不优雅，所以不喜欢这种方式。总之二叉搜索树不是唯一的，解法也不是只有一种。
此外，代码除了迭代还可使用递归的实现方式，同样可参考上面的solution，但递归显然没有迭代的方式性能高效。

class Solution {
 public:
  TreeNode* deleteNode(TreeNode* root, int key) {
    TreeNode* cur = root;
    TreeNode* pre = nullptr;

    // find
    while (cur && key != cur->val) {
      pre = cur;
      if (key < cur->val) {
        cur = cur->left;
      } else {
        cur = cur->right;
      }
    }
    if (!cur) {
      return root;
    }

    // simple cases
    if (!cur->left || !cur->right) {
      if (!pre) {
        // The root node is the target node
        root = cur->left ? cur->left : cur->right;
      } else {
        (pre->val > cur->val ? pre->left : pre->right) =
            (cur->left ? cur->left : cur->right);
      }
      delete cur;
      return root;
    }

    // the target node has two children
    // find the left most node in the right subtree
    TreeNode* right = cur->right;
    pre = cur;
    while (right->left) {
      pre = right;
      right = right->left;
    }

    // get the value
    cur->val = right->val;

    // move the left most node found
    (pre->val > right->val ? pre->left : pre->right) = right->right;
    delete right;

    return root;
  }
};

[669] Trim a Binary Search Tree

题目描述。
Medium但是写起来意外的很简单。如果当前节点在范围外就对对应方向子树进行递归，如果在范围内就直接两端递归一下即可，没什么难度。

class Solution {
 public:
  TreeNode* trimBST(TreeNode* root, int low, int high) {
    if (!root) {
      return nullptr;
    }
    if (root->val < low) {
      return trimBST(root->right, low, high);
    }
    if (root->val > high) {
      return trimBST(root->left, low, high);
    }
    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
  }
};

[108] Convert Sorted Array to Binary Search Tree

题目描述。
数组已经是有序了，所以直接递归找区间中值二分即可，没什么难度。

class Solution {
 public:
  TreeNode* buildTree(vector<int>& nums, int left, int right) {
    if (left >= right) {
      return nullptr;
    }
    // we can use `int mid = left + ((right - left) / 2);` instead to avoid
    // int overflow.
    int mid = (left + right) / 2;
    TreeNode* cur = new TreeNode(nums[mid]);
    cur->left = buildTree(nums, left, mid);
    cur->right = buildTree(nums, mid + 1, right);
    return cur;
  }

  TreeNode* sortedArrayToBST(vector<int>& nums) {
    return buildTree(nums, 0, nums.size());
  }
};

[538] Convert BST to Greater Tree

题目描述。
写出来代码异常简洁的Medium题。根据题目要求，使用反中序遍历（右中左）。在遍历过程中记录当前累加值sum，先算右边，右子树返回值累加到当前节点，再传到左子树去累加，最后把整个子树的累加值再传回父节点即可。
注意遍历到空节点的时候直接返回sum，即可从累加过的值继续累加。

class Solution {
 public:
  int traversal(TreeNode* cur, int sum) {
    if (!cur) {
      return sum;
    }
    cur->val += traversal(cur->right, sum);
    return traversal(cur->left, cur->val);
  }

  TreeNode* convertBST(TreeNode* root) {
    traversal(root, 0);
    return root;
  }
};

总结

这一部分刷的题比较多。概括起来的话就是

首先掌握二叉树的基本遍历方式，例如前中后序遍历和层序遍历，实现方式又分为递归法和迭代法，为了统一前中后序的迭代法实现方式又有统一迭代法。
大部分的题都只是对二叉树做遍历，然后在遍历的过程中记录和传递一些需要的中间数据即可。遍历的方式可根据题目要求来，迭代还是递归也可根据怎么实现方便怎么来。
[106] Construct Binary Tree from Inorder and Postorder Traversal要求通过中序和后序遍历的结果来还原构造出二叉树。这里我们要利用后序遍历的最后一个节点一定是根节点的性质，然后对应到中序遍历的位置来分割左右子树，再回到后序遍历的部分找子树的根节点，两个遍历结果来回分割和查询。注意前序遍历和中序遍历的结果也可以用来唯一确定一颗二叉树，但是前序和后序一起却不行，因为没有中序遍历无法确定左右部分，也就是无法分割。
后面的题是关于二叉搜索树（BST）的。BST的查找和插入都很简单，但删除有一定难度，这里使用了其右子树的最左节点来替换要删除的节点（其同时有左右儿子的情况）。此外就是可以注意一下BST的中序遍历的结果是有序序列的性质，在某些题目中会很有用。

AllenY's blog