解决问题思路有两个方向

=> 1. 利用遍历框架，在前中后位置加入新的逻辑

=> 2. 利用分解问题的思路，将问题分解为 当前结点 和 左右子树

前中后遍历

前序遍历：根节点 + 左子树前序遍历的结果 + 右子树前序遍历的结果

中序遍历：左子树中序遍历的结果 + 根节点 +  右子树中序遍历的结果

后序遍历：左子树后序遍历的结果 + 右子树后序遍历的结果 + 根节点

（是不是从文字上就能看出递归的猫腻？）

void Traverse(TreeNode* root) {if(!root) return;
//    前序位置Traverse(root->left);
//    中序位置Traverse(root->right);
//    后序位置
}

以前序遍历为例：

vector<int> res;
void Traverse(TreeNode* root) {if(!root) return;res.emplace_back(root->val);Traverse(root->left);Traverse(root->right);
}
vector<int> preorderTraverse(TreeNode* root) {Traverse(root);return res;
}

如果我想用从分解问题（其实就是分治）的角度去模拟前序遍历的结果呢？

vector<int> preorder(TreeNode* root) {vector<int> ans;if(!root) return ans;
//    前序遍历的结果：根节点 + 左子树前序遍历的结果 + 右子树前序遍历的结果（言下之意：层层向下拨开云雾至子叶点）vector<int> left = preorder(root->left);ans.insert(ans.end(), left.begin(), left.end());vector<int> right = preorder(root->right);ans.insert(ans.end(), right.begin(), right.end());return ans;
}

543. 二叉树的直径 - 力扣（LeetCode）

借助遍历框架解决问题

注意depth的定义：该层的深度大小

前序是刚来到这个结点 => 深度+1，后序是要离开这个结点啦 => 深度 - 1

// ans记录的是整个遍历下来depth的最大值
int ans = 0;
// depth记录的是该层的深度大小
int depth = 0;
void traverse(TreeNode* root) {if(!root) return;depth++;ans = max(ans, depth);traverse(root->left);traverse(root->right);depth--;
}
int maxDepthTraverse(TreeNode* root) {traverse(root);return ans;
}

分治思想解决问题

递归真是一种魔法！

=> 可以实现倒序

=> 可以用来拆分问题，把大问题拆解成一个一个能解决的小问题，综合一下，返回最终答案

这里每个maxLeft或者maxRight就看成一颗新的小一点的树继续执行这个任务

int maxDepthRecursion(TreeNode* root) {
//    分治if(!root) return 0;int maxLeft = maxDepthRecursion(root->left);int maxRight = maxDepthRecursion(root->right);
//    整棵树的最大深度 == 左右子树中的最大深度 + 1（根节点自己）return max(maxLeft, maxRight) + 1;
}

 再来深入理解一下后序位置的特殊性

前序位置的代码只能从函数参数中获取父节点传递来的数据，

后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据

一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写

 543. 二叉树的直径 - 力扣（LeetCode）

class Solution {
public:
//  理解题意：某一结点的直径 == 左子树深度 + 右子树深度
//  => 有没有读出 遍历 + 分治 的味道？int MaxDiameter = 0;int maxDepth(TreeNode* root) {if(!root) return 0;int leftMax = maxDepth(root->left);int rightMax = maxDepth(root->right);// 后序位置MaxDiameter = max(MaxDiameter, leftMax + rightMax);return max(leftMax, rightMax) + 1;}int diameterOfBinaryTree(TreeNode* root) {maxDepth(root);return MaxDiameter;}
};

层序遍历

从上到下遍历二叉树的每一层

从左到右遍历每一层的每个节点

迭代写法比较好理解

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