如果需要遍历整棵树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！

101. 对称二叉树

  1. else if (left->val != right->val) return false

注意判断特殊情况
类似题目：
100.相同的树
572. 另一棵树的子树

  1. // 其中isSameTree就是判断相同的树的逻辑
  2. bool isSubtree(TreeNode* root, TreeNode* subRoot) {
  3.      if (root == nullptr && subRoot != nullptr) return false;
  4.      else if (root == nullptr && subRoot == nullptr) return true;
  6.      return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
  7. }
  8. 这里非常巧妙，调用自身来判断(root->left, subRoot)和(root->right, subRoot)

104. 二叉树的最大深度

  1. depth = 1 + max(leftdepth, rightdepth);

左右子树最大深度

111. 二叉树的最小深度

  1. // 当一个左子树为空，右不为空，这时并不是最低点
  2. if (node->left == NULL && node->right != NULL) { 
  3.     return 1 + rightDepth;
  4. }   
  5. // 当一个右子树为空，左不为空，这时并不是最低点
  6. if (node->left != NULL && node->right == NULL) { 
  7.     return 1 + leftDepth;
  8. }
  9. int result = 1 + min(leftDepth, rightDepth);

注意：当某个节点的左右子树均为空时，才算是最小深度的节点。

222. 完全二叉树的节点个数

注意完全二叉树的节点总数的计算公式。

  1. if (depthLeft == depthRight) {
  2.    return (2 << depthLeft) - 1;
  3. }

110. 平衡二叉树

这道题还是不能自己独立的写出来递归解法。一直觉得这道题真不是“简单”。
对理解递归的过程理解很有帮助
还是需要多理几遍递归的执行过程。

  1. class Solution {
  2. public:
  3.     int getDepth(TreeNode* root) {
  4.         if (root == nullptr) return 0;
  6.         int depthLeft = getDepth(root->left);
  7.         if (depthLeft == -1) return -1;
  8.         int depthRight = getDepth(root->right);
  9.         if (depthRight == -1) return -1;
  11.         int result = 0;
  12.         if (abs(depthLeft - depthRight) > 1) return -1;
  13.         else {
  14.             return 1 + max(depthLeft, depthRight);
  15.         }
  16.     }
  17.     bool isBalanced(TreeNode* root) {
  18.         int result = getDepth(root);
  20.         return result == - 1 ? false : true;
  21.     }
  22. };

257. 二叉树的所有路径

因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。
然后是递归和回溯的过程，上面说过没有判断cur是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了。
回溯和递归是一一对应的，有一个递归，就要有一个回溯

  1. class Solution {
  2. public:
  3.     void backtracking(TreeNode* root, vector<string>& ans, vector<int>& vec) {
  4.         vec.push_back(root->val);  // 前序遍历
  5.         if (root->left == nullptr && root->right == nullptr) {
  6.             string str;
  7.             int len = vec.size();
  8.             for (int i = 0; i < len - 1; i++) {
  9.                 str += std::to_string(vec[i]) + "->";
  10.             }
  11.             str += std::to_string(vec[len - 1]);
  12.             ans.push_back(str);
  13.         }
  15.         if (root->left) { // 判空
  16.             backtracking(root->left, ans, vec);
  17.             vec.pop_back();  // 回溯和递归一一绑定
  18.         }
  19.         if (root->right) {
  20.             backtracking(root->right, ans, vec);
  21.             vec.pop_back();
  22.         }
  23.     }
  24.     vector<string> binaryTreePaths(TreeNode* root) {
  25.         vector<int> vec;
  26.         vector<string> ans;
  27.         backtracking(root, ans, vec);
  29.         return ans;
  30.     }
  31. };

404.左叶子之和

定义：如果左节点不为空，且左节点没有左右孩子，那么这个节点的左节点就是左叶子
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，判断代码如下：

  1. if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
  2.     左叶子节点处理逻辑
  3. }