给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
输入：root = [3,9,20,null,null,15,7]
C++代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public : vector<vector<int >> levelOrderBottom (TreeNode *root) { queue<TreeNode *> que; if (root != nullptr ) que.push (root); vector<vector<int >> res; while (!que.empty ()) { int size = que.size (); vector<int > vec; for (int i = 0 ; i < size; i++) { TreeNode *cur = que.front (); que.pop (); vec.push_back (cur->val); if (cur->left) que.push (cur->left); if (cur->right) que.push (cur->right); } res.insert (res.begin (), vec); } return res; } };
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
C++代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public : vector<int > rightSideView (TreeNode *root) { queue<TreeNode *> que; if (root != nullptr ) que.push (root); vector<int > vec; while (!que.empty ()) { vec.push_back (que.back ()->val); int size = que.size (); for (int i = 0 ; i < size; i++) { TreeNode *cur = que.front (); que.pop (); if (cur->left) que.push (cur->left); if (cur->right) que.push (cur->right); } } return vec; } };
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
输入：root = [3,9,20,null,null,15,7]
C++代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : vector<double > averageOfLevels (TreeNode* root) { vector<double > res; queue<TreeNode*> que; que.push (root); while (!que.empty ()){ int size = que.size (); double vals = 0 ; for (int i = 0 ; i < size; i++) { TreeNode* cur = que.front (); que.pop (); vals += cur->val; if (cur->left) que.push (cur->left); if (cur->right) que.push (cur->right); } res.push_back (vals/size); } return res; } };
给定一个 N 叉树，返回其节点值的层序遍历 。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
输入：root = [1,null,3,2,4,null,5,6]
C++代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public : vector<vector<int >> levelOrder (Node *root) { vector<vector<int >> res; queue<Node *> que; if (root != nullptr ) que.push (root); while (!que.empty ()) { int size = que.size (); vector<int > vec; for (int i = 0 ; i < size; i++) { Node *cur = que.front (); vec.push_back (cur->val); que.pop (); for (Node *child : cur->children) { que.push (child); } } res.push_back (vec); } return res; } };
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
输入: root = [1,3,2,5,3,null,9]
C++代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : vector<int > largestValues (TreeNode* root) { queue<TreeNode*> que; if (root != nullptr ) que.push (root); vector<int > res; while (!que.empty ()) { int max = INT_MIN; int size = que.size (); for (int i = 0 ; i < size; i++) { TreeNode* cur = que.front (); que.pop (); if (cur->left) que.push (cur->left); if (cur->right) que.push (cur->right); max = cur->val > max ? cur->val : max; } res.push_back (max); } return res; } };
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
1 2 3 4 5 6 struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
1 2 3 输入：root = [1,2,3,4,5,6,7] 输出：[1,#,2,3,#,4,5,6,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
C++代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public : Node *connect (Node *root) { queue<Node *> que; if (root != nullptr ) que.push (root); while (!que.empty ()) { int size = que.size (); for (int i = 0 ; i < size; i++) { Node *cur = que.front (); que.pop (); if (i < size - 1 ) cur->next = que.front (); if (cur->left) que.push (cur->left); if (cur->right) que.push (cur->right); } } return root; } };
给定一个二叉树：
1 2 3 4 5 6 struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。
1 2 3 输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
思路
C++代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public : Node *connect (Node *root) { queue<Node *> que; if (root != nullptr ) que.push (root); while (!que.empty ()) { int size = que.size (); for (int i = 0 ; i < size; i++) { Node *cur = que.front (); que.pop (); if (i < size - 1 ) cur->next = que.front (); if (cur->left) que.push (cur->left); if (cur->right) que.push (cur->right); } } return root; } };
101.对称二叉树
力扣题目链接
给定一个二叉树，检查它是否是镜像对称的。
思路
对称二叉树定义： 对于树中 任意两个对称节点 L 和 R ，一定有：
L.val = R.val ：即此两对称节点值相等。L.left.val = R.right.val ：即 L.right.val = R.left.val ：即
根据以上规律，考虑从顶至底递归，判断每对左右节点是否对称，从而判断树是否为对称二叉树。
那么遍历的顺序应该是什么样的呢？
本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。
其实后序也可以理解为是一种回溯，当然这是题外话，讲回溯的时候会重点讲的。
说到这大家可能感觉我有点啰嗦，哪有这么多道理，上来就干就完事了。别急，我说的这些在下面的代码讲解中都有身影。
那么我们先来看看递归法的代码应该怎么写。
递归法
递归三部曲
确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。
代码如下：
1 bool compare(TreeNode* left, TreeNode* right)
确定终止条件
要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点 ）
左节点为空，右节点不为空，不对称，return false
左不为空，右为空，不对称 return false
左右都为空，对称，返回true
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
左右都不为空，比较节点数值，不相同就return false
此时左右节点不为空，且数值也不相同的情况我们也处理了。
代码如下：
1 2 3 4 if (left == NULL && right != NULL ) return false ;else if (left != NULL && right == NULL ) return false ;else if (left == NULL && right == NULL ) return true ;else if (left->val != right->val) return false ;
注意上面最后一种情况，我没有使用else，而是else if， 因为我们把以上情况都排除之后，剩下的就是 左右节点都不为空，且数值相同的情况。
确定单层递归的逻辑
此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
如果左右都对称就返回true ，有一侧不对称就返回false 。
代码如下：
1 2 3 4 bool outside = compare (left->left, right->right); bool inside = compare (left->right, right->left); bool isSame = outside && inside; return isSame;
如上代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为“后序遍历”（尽管不是严格的后序遍历）。
最后递归的C++整体代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : bool compare (TreeNode* left, TreeNode* right) if (left == NULL && right != NULL ) return false ; else if (left != NULL && right == NULL ) return false ; else if (left == NULL && right == NULL ) return true ; else if (left->val != right->val) return false ; bool outside = compare (left->left, right->right); bool inside = compare (left->right, right->left); bool isSame = outside && inside; return isSame; } bool isSymmetric (TreeNode* root) if (root == NULL ) return true ; return compare (root->left, root->right); } };
当然我可以把如上代码整理如下：
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : bool isSymmetric (TreeNode* root) return root == nullptr || recur (root->left, root->right); } private : bool recur (TreeNode* L, TreeNode* R) if (L == nullptr && R == nullptr ) return true ; if (L == nullptr || R == nullptr || L->val != R->val) return false ; return recur (L->left, R->right) && recur (L->right, R->left); } };
这个代码就很简洁了，但隐藏了很多逻辑，条理不清晰，而且递归三部曲，在这里完全体现不出来。
所以建议大家做题的时候，一定要想清楚逻辑，每一步做什么。把题目所有情况想到位，相应的代码写出来之后，再去追求简洁代码的效果。
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
返回它的最大深度 3 。
思路
递归法
本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
而根节点的高度就是二叉树的最大深度 ，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
先用后序遍历（左右中）来计算树的高度。
确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
代码如下：
1 int getdepth (TreeNode* node)
确定终止条件：如果为空节点的话，就返回0，表示高度为0。
1 if (node == NULL ) return 0 ;
确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
1 2 3 4 int leftdepth = getdepth (node->left); int rightdepth = getdepth (node->right); int depth = 1 + max (leftdepth, rightdepth); return depth;
所以整体c++代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 class solution {public : int getdepth (TreeNode* node) if (node == NULL ) return 0 ; int leftdepth = getdepth (node->left); int rightdepth = getdepth (node->right); int depth = 1 + max (leftdepth, rightdepth); return depth; } int maxDepth (TreeNode* root) return getdepth (root); } };
代码精简之后c++代码如下：
1 2 3 4 5 6 7 8 class solution {public : int maxDepth (TreeNode* root) if (root == null) return 0 ; return 1 + max (maxDepth (root->left), maxDepth (root->right)); } };
精简之后的代码根本看不出是哪种遍历方式，也看不出递归三部曲的步骤，所以如果对二叉树的操作还不熟练，尽量不要直接照着精简代码来学。
迭代法
使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。
在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度.
c++代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class solution {public : int maxDepth (TreeNode* root) if (root == NULL ) return 0 ; int depth = 0 ; queue<TreeNode*> que; que.push (root); while (!que.empty ()) { int size = que.size (); depth++; for (int i = 0 ; i < size; i++) { TreeNode* node = que.front (); que.pop (); if (node->left) que.push (node->left); if (node->right) que.push (node->right); } } return depth; } };
559.n叉树的最大深度
力扣题目链接
给定一个 n 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如，给定一个 3叉树 :
我们应返回其最大深度，3。
思路
依然可以提供递归法和迭代法，来解决这个问题，思路是和二叉树思路一样的，直接给出代码如下：
递归法
c++代码：
1 2 3 4 5 6 7 8 9 10 11 class solution {public : int maxDepth (Node* root) if (root == 0 ) return 0 ; int depth = 0 ; for (Node* child : root->children) { depth = max (maxDepth (child), depth); } return depth + 1 ; } };
迭代法
依然是层序遍历，代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class solution {public : int maxDepth (Node* root) queue<Node*> que; if (root != NULL ) que.push (root); int depth = 0 ; while (!que.empty ()) { int size = que.size (); depth++; for (int i = 0 ; i < size; i++) { Node* node = que.front (); que.pop (); for (auto child : cur->children) { if (child) que.push (child); } } } return depth; } };
111.二叉树最小深度
力扣题目链接
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最小深度 2.
思路
直觉上好像和求最大深度差不多，其实还是差不少的。
本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离 也同样是最小深度。
以下讲解中遍历顺序上依然采用后序遍历（因为要比较递归返回之后的结果，本文我也给出前序遍历的写法）。
本题还有一个误区，在处理节点的过程中，最大深度很容易理解，最小深度就不那么好理解，如图：
这就重新审题了，题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 ，注意是叶子节点 。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！
递归法
来来来，一起递归三部曲：
确定递归函数的参数和返回值
参数为要传入的二叉树根节点，返回的是int类型的深度。
代码如下：
1 int getDepth(TreeNode* node)
确定终止条件
终止条件也是遇到空节点返回0，表示当前节点的高度为0。
代码如下：
1 if (node == NULL) return 0;
确定单层递归的逻辑
这块和求最大深度可就不一样了，一些同学可能会写如下代码：
1 2 3 4 int leftDepth = getDepth(node->left); int rightDepth = getDepth(node->right); int result = 1 + min(leftDepth, rightDepth); return result;
这个代码就犯了此图中的误区：
如果这么求的话，没有左孩子的分支会算为最短深度。
所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 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;
遍历的顺序为后序（左右中），可以看出：求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
整体递归代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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); } };
精简之后代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int minDepth (TreeNode* root) if (root == NULL ) return 0 ; if (root->left == NULL && root->right != NULL ) { return 1 + minDepth (root->right); } if (root->left != NULL && root->right == NULL ) { return 1 + minDepth (root->left); } return 1 + min (minDepth (root->left), minDepth (root->right)); } };
精简之后的代码根本看不出是哪种遍历方式，所以依然还要强调一波：如果对二叉树的操作还不熟练，尽量不要直接照着精简代码来学。
迭代法
相对于104.二叉树的最大深度 ，本题还可以使用层序遍历的方式来解决，思路是一样的。
如果对层序遍历还不清楚的话，可以看这篇：二叉树：层序遍历登场！
需要注意的是，只有当左右孩子都为空的时候，才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点
代码如下：（详细注释）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : int minDepth (TreeNode* root) if (root == NULL ) return 0 ; int depth = 0 ; queue<TreeNode*> que; que.push (root); while (!que.empty ()) { int size = que.size (); depth++; for (int i = 0 ; i < size; i++) { TreeNode* node = que.front (); que.pop (); if (node->left) que.push (node->left); if (node->right) que.push (node->right); if (!node->left && !node->right) { return depth; } } } return depth; } };
222.完全二叉树的节点个数
力扣题目链接
给出一个完全二叉树，求出该树的节点个数。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
示例 3：
提示：
树中节点的数目范围是[0, 5 * 10^4]
0 <= Node.val <= 5 * 10^4
题目数据保证输入的树是 完全二叉树
思路
普通二叉树
首先按照普通二叉树的逻辑来求。
这道题目的递归法和求二叉树的深度写法类似， 而迭代法，二叉树：层序遍历登场！ 遍历模板稍稍修改一下，记录遍历的节点数量就可以了。
递归遍历的顺序依然是后序（左右中）。
递归
如果对求二叉树深度还不熟悉的话，看这篇：二叉树：看看这些树的最大深度 。
确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。
代码如下：
1 int getNodesNum(TreeNode* cur) {
确定终止条件：如果为空节点的话，就返回0，表示节点数为0。
代码如下：
1 if (cur == NULL) return 0;
确定单层递归的逻辑：先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
代码如下：
1 2 3 4 int leftNum = getNodesNum(cur->left); // 左 int rightNum = getNodesNum(cur->right); // 右 int treeNum = leftNum + rightNum + 1; // 中 return treeNum;
所以整体C++代码如下：
时间复杂度：
空间复杂度：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {private : int getNodesNum (TreeNode* cur) if (cur == NULL ) 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); } };
代码精简之后C++代码如下：
1 2 3 4 5 6 7 8 class Solution {public : int countNodes (TreeNode* root) if (root == NULL ) return 0 ; return 1 + countNodes (root->left) + countNodes (root->right); } };
迭代
如果对求二叉树层序遍历还不熟悉的话，看这篇：二叉树：层序遍历登场！ 。
那么只要模板少做改动，加一个变量result，统计节点数量就可以了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int countNodes (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 (); result++; if (node->left) que.push (node->left); if (node->right) que.push (node->right); } } return result; } };
110.平衡二叉树
力扣题目链接
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
返回 false 。
题外话
咋眼一看这道题目和104.二叉树的最大深度 很像，其实有很大区别。
这里强调一波概念：
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
但leetcode中强调的深度和高度很明显是按照节点来计算的，如图：
关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为一度，即根节点的深度是0，我们暂时以leetcode为准（毕竟要在这上面刷题）。
因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）
有的同学一定疑惑，为什么104.二叉树的最大深度 中求的是二叉树的最大深度，也用的是后序遍历。
那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这棵树的最大深度，所以才可以使用后序遍历。
在104.二叉树的最大深度 中，如果真正求取二叉树的最大深度，代码应该写成如下：（前序遍历）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : int result; void getDepth (TreeNode* node, int depth) result = depth > result ? depth : result; if (node->left == NULL && node->right == NULL ) return ; if (node->left) { depth++; getDepth (node->left, depth); depth--; } if (node->right) { depth++; getDepth (node->right, depth); depth--; } return ; } int maxDepth (TreeNode* root) result = 0 ; if (root == NULL ) return result; getDepth (root, 1 ); return result; } };
可以看出使用了前序（中左右）的遍历顺序，这才是真正求深度的逻辑！
注意以上代码是为了把细节体现出来，简化一下代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : int result; void getDepth (TreeNode* node, int depth) result = depth > result ? depth : result; if (node->left == NULL && node->right == NULL ) return ; if (node->left) { getDepth (node->left, depth + 1 ); } if (node->right) { getDepth (node->right, depth + 1 ); } return ; } int maxDepth (TreeNode* root) result = 0 ; if (root == 0 ) return result; getDepth (root, 1 ); return result; } };
递归
此时大家应该明白了既然要求比较高度，必然是要后序遍历。
递归三步曲分析：
明确递归函数的参数和返回值
参数：当前传入节点。
那么如何标记左右子树是否差值大于1呢？
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
代码如下：
1 2 int getHeight (TreeNode* node)
明确终止条件
递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
代码如下：
1 2 3 if (node == NULL ) { return 0 ; }
明确单层递归的逻辑
如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。
分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 int leftHeight = getHeight (node->left); if (leftHeight == -1 ) return -1 ;int rightHeight = getHeight (node->right); if (rightHeight == -1 ) return -1 ;int result;if (abs (leftHeight - rightHeight) > 1 ) { result = -1 ; } else { result = 1 + max (leftHeight, rightHeight); } return result;
代码精简之后如下：
1 2 3 4 5 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);
此时递归的函数就已经写出来了，这个递归的函数传入节点指针，返回以该节点为根节点的二叉树的高度，如果不是二叉平衡树，则返回-1。
getHeight整体代码如下：
1 2 3 4 5 6 7 8 9 10 int getHeight (TreeNode* node) if (node == NULL ) { 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); }
最后本题整体递归代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int getHeight (TreeNode* node) if (node == NULL ) { 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 ; } };
257. 二叉树的所有路径
力扣题目链接
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
思路
这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。
前序遍历以及回溯的过程如图：
我们先使用递归的方式，来做前序遍历。要知道递归和回溯就是一家的，本题也需要回溯。
递归
递归函数参数以及返回值
要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值，代码如下：
1 void traversal(TreeNode* cur, vector<int>& path, vector<string>& result)
确定递归终止条件
在写递归的时候都习惯了这么写：
1 2 3 if (cur == NULL) { 终止处理逻辑 }
但是本题的终止条件这样写会很麻烦，因为本题要找到叶子节点，就开始结束的处理逻辑了（把路径放进result里）。
那么什么时候算是找到了叶子节点？ 是当 cur不为空，其左右孩子都为空的时候，就找到叶子节点。
所以本题的终止条件是：
1 2 3 if (cur->left == NULL && cur->right == NULL) { 终止处理逻辑 }
为什么没有判断cur是否为空呢，因为下面的逻辑可以控制空节点不入循环。
再来看一下终止处理的逻辑。
这里使用vector<int> 结构path来记录路径，所以要把vector<int> 结构的path转为string格式，再把这个string 放进result里。
那么为什么使用了vector<int> 结构来记录路径呢？ 因为在下面处理单层递归逻辑的时候，要做回溯，使用vector方便来做回溯。
可能有的同学问了，我看有些人的代码也没有回溯啊。
其实是有回溯的，只不过隐藏在函数调用时的参数赋值里 ，下文我还会提到。
这里我们先使用vector<int>结构的path容器来记录路径，那么终止处理逻辑如下：
1 2 3 4 5 6 7 8 9 10 if (cur->left == NULL && cur->right == NULL ) { string sPath; for (int i = 0 ; i < path.size () - 1 ; i++) { sPath += to_string (path[i]); sPath += "->" ; } sPath += to_string (path[path.size () - 1 ]); result.push_back (sPath); return ; }
确定单层递归逻辑
因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。
path.push_back(cur->val);
然后是递归和回溯的过程，上面说过没有判断cur是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了。
所以递归前要加上判断语句，下面要递归的节点是否为空，如下
1 2 3 4 5 6 if (cur->left) { traversal(cur->left, path, result); } if (cur->right) { traversal(cur->right, path, result); }
此时还没完，递归完，要做回溯啊，因为path 不能一直加入节点，它还要删节点，然后才能加入新的节点。
那么回溯要怎么回溯呢，一些同学会这么写，如下：
1 2 3 4 5 6 7 if (cur->left) { traversal (cur->left, path, result); } if (cur->right) { traversal (cur->right, path, result); } path.pop_back ();
这个回溯就有很大的问题，我们知道，回溯和递归是一一对应的，有一个递归，就要有一个回溯 ，这么写的话相当于把递归和回溯拆开了， 一个在花括号里，一个在花括号外。
所以回溯要和递归永远在一起，世界上最遥远的距离是你在花括号里，而我在花括号外！
那么代码应该这么写：
1 2 3 4 5 6 7 8 if (cur->left) { traversal (cur->left, path, result); path.pop_back (); } if (cur->right) { traversal (cur->right, path, result); path.pop_back (); }
那么本题整体代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution {private : void traversal (TreeNode* cur, vector<int >& path, vector<string>& result) path.push_back (cur->val); if (cur->left == NULL && cur->right == NULL ) { string sPath; for (int i = 0 ; i < path.size () - 1 ; i++) { sPath += to_string (path[i]); sPath += "->" ; } sPath += to_string (path[path.size () - 1 ]); result.push_back (sPath); return ; } if (cur->left) { traversal (cur->left, path, result); path.pop_back (); } if (cur->right) { traversal (cur->right, path, result); path.pop_back (); } } public : vector<string> binaryTreePaths (TreeNode* root) { vector<string> result; vector<int > path; if (root == NULL ) return result; traversal (root, path, result); return result; } };
如上的C++代码充分体现了回溯。
那么如上代码可以精简成如下代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {private : void traversal (TreeNode* cur, string path, vector<string>& result) 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); } public : vector<string> binaryTreePaths (TreeNode* root) { vector<string> result; string path; if (root == NULL ) return result; traversal (root, path, result); return result; } };
注意在函数定义的时候void traversal(TreeNode* cur, string path, vector<string>& result) ，定义的是string path，每次都是复制赋值，不用使用引用，否则就无法做到回溯的效果。（这里涉及到C++语法知识）
那么在如上代码中，貌似没有看到回溯的逻辑，其实不然，回溯就隐藏在traversal(cur->left, path + "->", result);中的 path + "->"。 每次递归调用 traversal 函数时，都会创建一个新的 path 变量，path依然是没有加上"->" 的，这就是回溯了。
递归调用时的作用域： 当 traversal 函数递归调用自身时，每次调用都会创建一个新的局部变量 path，用于当前的递归分支。这个局部变量只在当前递归分支中有效，不会影响其他分支。当递归回到上一层时，之前的 path 变量会被销毁，回到上一个状态。
为了把这份精简代码的回溯过程展现出来，大家可以试一试把：
1 if (cur->left) traversal (cur->left, path + "->" , result);
改成如下代码：
1 2 path += "->" ; traversal (cur->left, path, result);
即：
1 2 3 4 5 6 7 8 if (cur->left) { path += "->" ; traversal (cur->left, path, result); } if (cur->right) { path += "->" ; traversal (cur->right, path, result); }
此时就没有回溯了，这个代码就是通过不了的了。
如果想把回溯加上，就要 在上面代码的基础上，加上回溯，就可以AC了。
1 2 3 4 5 6 7 8 9 10 11 12 if (cur->left) { path += "->" ; traversal (cur->left, path, result); path.pop_back (); path.pop_back (); } if (cur->right) { path += "->" ; traversal (cur->right, path, result); path.pop_back (); path.pop_back (); }
大家应该可以感受出来，如果把 path + "->"作为函数参数就是可以的，因为并没有改变path的数值，执行完递归函数之后，path依然是之前的数值（相当于回溯了）
综合以上，第二种递归的代码虽然精简但把很多重要的点隐藏在了代码细节里，第一种递归写法虽然代码多一些，但是把每一个逻辑处理都完整的展现出来了。
404.左叶子之和
力扣题目链接
计算给定二叉树的所有左叶子之和。
示例：
思路
首先要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历。
因为题目中其实没有说清楚左叶子究竟是什么节点，那么我来给出左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点
大家思考一下如下图中二叉树，左叶子之和究竟是多少？
其实是0，因为这棵树根本没有左叶子！
但看这个图的左叶子之和是多少？
相信通过这两个图，大家对最左叶子的定义有明确理解了。
那么判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，判断代码如下：
1 2 3 if (node->left != NULL && node->left->left == NULL && node->left->right == NULL ) { 左叶子节点处理逻辑 }
递归法
递归的遍历顺序为后序遍历（左右中），是因为要通过递归函数的返回值来累加求取左叶子数值之和。
递归v三部曲：
确定递归函数的参数和返回值
判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int
使用题目中给出的函数就可以了。
确定终止条件
如果遍历到空节点，那么左叶子值一定是0
1 if (root == NULL ) return 0 ;
注意，只有当前遍历的节点是父节点，才能判断其子节点是不是左叶子。 所以如果当前遍历的节点是叶子节点，那其左叶子也必定是0，那么终止条件为：
1 2 if (root == NULL ) return 0 ;if (root->left == NULL && root->right== NULL ) return 0 ;
确定单层递归的逻辑
当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。
代码如下：
1 2 3 4 5 6 7 8 9 int leftValue = sumOfLeftLeaves (root->left); if (root->left && !root->left->left && !root->left->right) { leftValue = root->left->val; } int rightValue = sumOfLeftLeaves (root->right); int sum = leftValue + rightValue; return sum;
整体递归代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int sumOfLeftLeaves (TreeNode* root) if (root == NULL ) return 0 ; if (root->left == NULL && root->right== NULL ) return 0 ; int leftValue = sumOfLeftLeaves (root->left); if (root->left && !root->left->left && !root->left->right) { leftValue = root->left->val; } int rightValue = sumOfLeftLeaves (root->right); int sum = leftValue + rightValue; return sum; } };
以上代码精简之后如下：
1 2 3 4 5 6 7 8 9 10 11 class Solution {public : int sumOfLeftLeaves (TreeNode* root) if (root == NULL ) return 0 ; int leftValue = 0 ; if (root->left != NULL && root->left->left == NULL && root->left->right == NULL ) { leftValue = root->left->val; } return leftValue + sumOfLeftLeaves (root->left) + sumOfLeftLeaves (root->right); } };
精简之后的代码其实看不出来用的是什么遍历方式了，对于算法初学者以上根据第一个版本来学习。
迭代法
本题迭代法使用前中后序都是可以的，只要把左叶子节点统计出来，就可以了，那么参考文章 二叉树：听说递归能做的，栈也能做！ 和二叉树：迭代法统一写法 中的写法，可以写出一个前序遍历的迭代法。
判断条件都是一样的，代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int sumOfLeftLeaves (TreeNode* root) stack<TreeNode*> st; if (root == NULL ) return 0 ; st.push (root); int result = 0 ; while (!st.empty ()) { TreeNode* node = st.top (); st.pop (); if (node->left != NULL && node->left->left == NULL && node->left->right == NULL ) { result += node->left->val; } if (node->right) st.push (node->right); if (node->left) st.push (node->left); } return result; } };
总结
这道题目要求左叶子之和，其实是比较绕的，因为不能判断本节点是不是左叶子节点。
此时就要通过节点的父节点来判断其左孩子是不是左叶子了。
平时我们解二叉树的题目时，已经习惯了通过节点的左右孩子判断本节点的属性，而本题我们要通过节点的父节点判断本节点的属性。
希望通过这道题目，可以扩展大家对二叉树的解题思路。
513.找树左下角的值
力扣题目链接
给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:
示例 2:
迭代法
本题使用层序遍历再合适不过了，比递归要好理解得多！
只需要记录最后一行第一个节点的数值就可以了。
如果对层序遍历不了解，看这篇二叉树：层序遍历登场！ ，这篇里也给出了层序遍历的模板，稍作修改就一过刷了这道题了。
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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; } };
112. 路径总和
力扣题目链接
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
递归
可以使用深度优先遍历的方式（本题前中后序都可以，无所谓，因为中节点也没有处理逻辑）来遍历二叉树
确定递归函数的参数和返回类型
参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。
再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 中介绍）
如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
而本题我们要找一条符合条件的路径，所以递归函数需要返回值，及时返回，那么返回类型是什么呢？
如图所示：
图中可以看出，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。
所以代码如下：
1 bool traversal (treenode* cur, int count)
确定终止条件
首先计数器如何统计这一条路径的和呢？
不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
如果遍历到了叶子节点，count不为0，就是没找到。
递归终止条件代码如下：
1 2 if (!cur->left && !cur->right && count == 0 ) return true ; if (!cur->left && !cur->right) return false ;
确定单层递归的逻辑
因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。
递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。
代码如下：
1 2 3 4 5 6 7 8 9 if (cur->left) { if (traversal (cur->left, count - cur->left->val)) return true ; } if (cur->right) { if (traversal (cur->right, count - cur->right->val)) return true ; } return false ;
以上代码中是包含着回溯的，没有回溯，如何后撤重新找另一条路径呢。
回溯隐藏在traversal(cur->left, count - cur->left->val)这里， 因为把count - cur->left->val 直接作为参数传进去，函数结束，count的数值没有改变。
为了把回溯的过程体现出来，可以改为如下代码：
1 2 3 4 5 6 7 8 9 10 11 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 ;
整体代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {private : bool traversal (TreeNode* cur, int count) if (!cur->left && !cur->right && count == 0 ) return true ; 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); } };
以上代码精简之后如下：
1 2 3 4 5 6 7 8 9 10 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); } };
是不是发现精简之后的代码，已经完全看不出分析的过程了，所以我们要把题目分析清楚之后，再追求代码精简。 这一点我已经强调很多次了！
迭代
如果使用栈模拟递归的话，那么如果做回溯呢？
此时栈里一个元素不仅要记录该节点指针，还要记录从头结点到该节点的路径数值总和。
c++就我们用pair结构来存放这个栈里的元素。
定义为：pair<TreeNode*, int> pair<节点指针，路径数值>
这个为栈里的一个元素。
如下代码是使用栈模拟的前序遍历，如下：（详细注释）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class solution {public : bool haspathsum (TreeNode* root, int sum) if (root == null) return false ; stack<pair<TreeNode*, int >> st; st.push (pair <TreeNode*, int >(root, root->val)); while (!st.empty ()) { pair<TreeNode*, int > node = st.top (); st.pop (); if (!node.first->left && !node.first->right && sum == node.second) return true ; if (node.first->right) { st.push (pair <TreeNode*, int >(node.first->right, node.second + node.first->right->val)); } if (node.first->left) { st.push (pair <TreeNode*, int >(node.first->left, node.second + node.first->left->val)); } } return false ; } };
如果大家完全理解了本题的递归方法之后，就可以顺便把leetcode上113. 路径总和ii做了。
