Leetcode记录：二叉树例题
层序遍历
每道题都可以很简单地用层序遍历解答，以下只是放一些其他思路。
二叉树的右视图
Leetcode 199.给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
我们对树进行深度优先搜索，在搜索过程中，我们总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。这样一来，我们可以存储在每个深度访问的第一个结点，一旦我们知道了树的层数，就可以得到最终的结果数组：
vector<int> rightSideView(TreeNode* root) {
unordered_map<int, int> rightmostValueAtDepth;
int max_depth = -1;
stack<TreeNode*> nodeStack;
stack<int> depthStack;
nodeStack.push(root);
depthStack.push(0);
while (!nodeStack.empty()) {
TreeNode* node = nodeStack.top();nodeStack.pop();
int depth = depthStack.top();depthStack.pop();
if (node != NULL) {
// 维护二叉树的最大深度
max_depth = max(max_depth, depth);
// 如果不存在对应深度的节点我们才插入
if (rightmostValueAtDepth.find(depth) == rightmostValueAtDepth.end()) {
rightmostValueAtDepth[depth] = node -> val;
}
nodeStack.push(node -> left);
nodeStack.push(node -> right);
depthStack.push(depth + 1);
depthStack.push(depth + 1);
}
}
vector<int> rightView;
for (int depth = 0; depth <= max_depth; ++depth) {
rightView.push_back(rightmostValueAtDepth[depth]);
}
return rightView;
}
也可以执行执行广度优先搜索，左结点排在右结点之前，这样，我们对每一层都从左到右访问。因此，只保留每个深度最后访问的结点，我们就可以在遍历完整棵树后得到每个深度最右的结点：
vector<int> rightSideView(TreeNode* root) {
unordered_map<int, int> rightmostValueAtDepth;
int max_depth = -1;
queue<TreeNode*> nodeQueue;
queue<int> depthQueue;
nodeQueue.push(root);
depthQueue.push(0);
while (!nodeQueue.empty()) {
TreeNode* node = nodeQueue.front();nodeQueue.pop();
int depth = depthQueue.front();depthQueue.pop();
if (node != NULL) {
// 维护二叉树的最大深度
max_depth = max(max_depth, depth);
// 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
rightmostValueAtDepth[depth] = node -> val;
nodeQueue.push(node -> left);
nodeQueue.push(node -> right);
depthQueue.push(depth + 1);
depthQueue.push(depth + 1);
}
}
vector<int> rightView;
for (int depth = 0; depth <= max_depth; ++depth) {
rightView.push_back(rightmostValueAtDepth[depth]);
}
return rightView;
}
每层的平均值
Leetcode 637. 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。
递归dfs求解就是构造一个helper函数进行递归，将当前节点、所需要记录的数据以及深度depth作为参数传入，一个一个元素进行处理，其中还要注意每一层的第一个节点要进行特殊处理。
vector<double> averageOfLevels(TreeNode* root) {
auto counts = vector<int>();
auto sums = vector<double>();
dfs(root, 0, counts, sums);
auto averages = vector<double>();
int size = sums.size();
for (int i = 0; i < size; i++) {
averages.push_back(sums[i] / counts[i]);
}
return averages;
}
void dfs(TreeNode* root, int level, vector<int> &counts, vector<double> &sums) {
if (root == nullptr) {
return;
}
if (level < sums.size()) {
sums[level] += root->val;
counts[level] += 1;
} else {
sums.push_back(1.0 * root->val);
counts.push_back(1);
}
dfs(root->left, level + 1, counts, sums);
dfs(root->right, level + 1, counts, sums);
}
填充每个节点的下一个右侧节点指针
Leetcode 116. 给定一个完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
除了层序遍历外，也可以考虑使用已建立的 next 指针：第 N 层节点之间建立 next 指针后，再建立第 N+1 层节点的 next 指针。可以通过 next 指针访问同一层的所有节点，因此可以使用第 N 层的 next 指针，为第 N+1 层节点建立 next 指针。
Node* connect(Node* root) {
if (root == nullptr) {
return root;
}
// 从根节点开始
Node* leftmost = root;
while (leftmost->left != nullptr) {
// 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
Node* head = leftmost;
while (head != nullptr) {
// CONNECTION 1
head->left->next = head->right;
// CONNECTION 2
if (head->next != nullptr) {
head->right->next = head->next->left;
}
// 指针向后移动
head = head->next;
}
// 去下一层的最左的节点
leftmost = leftmost->left;
}
return root;
}
如果不是完美二叉树，也就是Leetcode 117题，也是可以用该思路：
void handle(Node* &last, Node* &p, Node* &nextStart) {
if (last) {
last->next = p;
}
if (!nextStart) {
nextStart = p;
}
last = p;
}
Node* connect(Node* root) {
if (!root) {
return nullptr;
}
Node *start = root;
while (start) {
Node *last = nullptr, *nextStart = nullptr;
for (Node *p = start; p != nullptr; p = p->next) {
if (p->left) {
handle(last, p->left, nextStart);
}
if (p->right) {
handle(last, p->right, nextStart);
}
}
start = nextStart;
}
return root;
}
二叉树属性
对称二叉树
Leetcode 101. 给你一个二叉树的根节点 root ， 检查它是否轴对称。
递归方法一定要注意三步走：确定递归函数的参数和返回值，确定终止条件，确定单层递归的逻辑。
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);
}
用队列或栈存放要比较的结点，两两拿出比较也是可以的。
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
queue<TreeNode*> que;
que.push(root->left); // 将左子树头结点加入队列
que.push(root->right); // 将右子树头结点加入队列
while (!que.empty()) { // 接下来就要判断这两个树是否相互翻转
TreeNode* leftNode = que.front(); que.pop();
TreeNode* rightNode = que.front(); que.pop();
if (!leftNode && !rightNode) { // 左节点为空、右节点为空，此时说明是对称的
continue;
}
// 左右一个节点不为空，或者都不为空但数值不相同，返回false
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
que.push(leftNode->left); // 加入左节点左孩子
que.push(rightNode->right); // 加入右节点右孩子
que.push(leftNode->right); // 加入左节点右孩子
que.push(rightNode->left); // 加入右节点左孩子
}
return true;
}
二叉树的最大深度
Leetcode 104. 给定一个二叉树 root ，返回其最大深度。 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
使用前序求的就是深度，使用后序求的是高度。
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）。 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）。 而根节点的高度就是二叉树的最大深度。
后序递归方法很简单：
int maxDepth(TreeNode* root) {
if (root == null) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
也可以使用前序递归：
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++; // 深度+1
getdepth(node->left, depth);
depth--; // 回溯，深度-1
}
if (node->right) { // 右
depth++; // 深度+1
getdepth(node->right, depth);
depth--; // 回溯，深度-1
}
return ;
}
int maxDepth(TreeNode* root) {
result = 0;
if (root == NULL) return result;
getdepth(root, 1);
return result;
}
也可以采用层序遍历的方法：
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;
}
n叉树的最大深度
Leetcode 559. 给定一个 n 叉树，找到其最大深度。
思路一模一样：
int maxDepth(Node* root) {
if(root ==nullptr)
return 0;
int depth = 0;
for(auto &node : root->children){
depth = max(depth, maxDepth(node));
}
return depth+1;
}
二叉树的最小深度
Leetcode 111. 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
思路是类似的，也可以采用前序遍历、后序遍历以及层序遍历来求解，但是要注意和最大深度不同的是，最小深度是从根节点到最近叶子节点的最短路径上的节点数量，在处理左右孩子不为空的逻辑上是不相同。
后序（左右中）遍历版本如下：
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));
}
前序遍历版本：
int result;
void getdepth(TreeNode* node, int depth) {
// 函数递归终止条件
if (node == nullptr) {
return;
}
// 中，处理逻辑：判断是不是叶子结点
if (node -> left == nullptr && node->right == nullptr) {
result = min(result, depth);
}
if (node->left) { // 左
getdepth(node->left, depth + 1);
}
if (node->right) { // 右
getdepth(node->right, depth + 1);
}
return ;
}
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
result = INT_MAX;
getdepth(root, 1);
return result;
}
层序遍历版本：需要注意的是，只有当左右孩子都为空的时候，才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点
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;
}
平衡二叉树
给定一个二叉树，判断它是否是平衡二叉树。
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
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;
}
二叉树的所有路径
Leetcode 257. 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
可以用深度优先，也可以用广度优先，只需要多一个记录path的队列即可。
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); // 右
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
路径之和 （递归回溯典型）
Leetcode 113.给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
vector<vector<int>> result;
vector<int> path;
// 递归函数不需要返回值，因为我们要遍历整个树
void traversal(TreeNode* cur, int count) {
if (!cur->left && !cur->right && count == 0) { // 遇到了叶子节点且找到了和为sum的路径
result.push_back(path);
return;
}
if (!cur->left && !cur->right) return ; // 遇到叶子节点而没有找到合适的边，直接返回
if (cur->left) { // 左 （空节点不遍历）
path.push_back(cur->left->val);
count -= cur->left->val;
traversal(cur->left, count); // 递归
count += cur->left->val; // 回溯
path.pop_back(); // 回溯
}
if (cur->right) { // 右 （空节点不遍历）
path.push_back(cur->right->val);
count -= cur->right->val;
traversal(cur->right, count); // 递归
count += cur->right->val; // 回溯
path.pop_back(); // 回溯
}
return ;
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
result.clear();
path.clear();
if (root == NULL) return result;
path.push_back(root->val); // 把根节点放进路径
traversal(root, sum - root->val);
return result;
}
左叶子之和
Leetcode 404. 给定二叉树的根节点 root ，返回所有左叶子之和。
同样的，dfs和bfs都可以的。
找树左下角的值
Leetcode 513. 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
两种方法都是可以的，bfs更简单，只需要每层第一个更新一下result就可以了，递归的dfs如下：
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;
}
二叉树修改与构造
翻转二叉树
Leetcode 226. 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
本质上还是遍历，深度优先和广度优先都是可以的。
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
swap(root->left, root->right); // 中
invertTree(root->left); // 左
invertTree(root->right); // 右
return root;
}
根据前序遍历和中序遍历构造二叉树
可以先利用递归的思想： 第一步：如果数组大小为零的话，说明是空节点了。 第二步：如果不为空，那么取前序数组第一个元素作为节点元素。 第三步：找到前序数组第一个元素在中序数组的位置，作为切割点 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组） 第五步：切割前序数组，切成前序左数组和前序右数组 第六步：递归处理左区间和右区间
TreeNode *helper(vector<int>& preorder, vector<int>& inorder){
int num = preorder.size();
if(num == 0) return nullptr;
TreeNode * root = new TreeNode(preorder.front());
if(num == 1) return root;
int part;
for(int i = 0; i < num; ++i){
if(inorder[i] == preorder.front())
part = i;
}
vector<int> leftIn(inorder.begin(), inorder.begin()+part);
vector<int> rightIn(inorder.begin()+part+1, inorder.end());
vector<int> leftPre(preorder.begin()+1, preorder.begin()+1+part);
vector<int> rightPre(preorder.begin()+1+part, preorder.end());
root->left = helper(leftPre,leftIn);
root->right = helper(rightPre,rightIn);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return helper(preorder,inorder);
}
迭代的思想也很巧妙：对于前序遍历中的任意两个连续节点 u 和 v，根据前序遍历的流程，我们可以知道 u 和 v 只有两种可能的关系：
- v 是 u 的左儿子。这是因为在遍历到 u 之后，下一个遍历的节点就是 u 的左儿子，即 v；
- u 没有左儿子，并且 v 是 u 的某个祖先节点（或者 u 本身）的右儿子。如果 u 没有左儿子，那么下一个遍历的节点就是 u 的右儿子。如果 u 没有右儿子，我们就会向上回溯，直到遇到第一个有右儿子（且 u 不在它的右儿子的子树中）的节点 ua，那么 v 就是 ua 的右儿子。 因此：
- 我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点；
- 我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向右移动 index，并将当前节点作为最后一个弹出的节点的右儿子；如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的左儿子；
- 无论是哪一种情况，我们最后都将当前的节点入栈。
给定中序和后序也可以按照此思路来做，先将两个数组翻转过来，构成 右中左 和 中右左 即可。
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (!preorder.size()) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[0]);
stack<TreeNode*> stk;
stk.push(root);
int inorderIndex = 0;
for (int i = 1; i < preorder.size(); ++i) {
int preorderVal = preorder[i];
TreeNode* node = stk.top();
if (node->val != inorder[inorderIndex]) {
node->left = new TreeNode(preorderVal);
stk.push(node->left);
}
else {
while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {
node = stk.top();
stk.pop();
++inorderIndex;
}
node->right = new TreeNode(preorderVal);
stk.push(node->right);
}
}
return root;
}