二叉树 · C++技术

[TOC] ## 二叉树 ### 知识点 **前序遍历**：先访问根节点，再前序遍历左子树，然后前序遍历右子树 **中序遍历**：先中序遍历左子树，再访问根节点，然后中序遍历右子树 **后序遍历**：先后续遍历左子树，再后续遍历右子树，然后访问根节点注意： * 以根节点访问顺序决定什么遍历 * 左子树都是优于右子树 #### 前序遍历 ``` struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; void preorderTraversal(TreeNode* root) { if (root == NULL) return; cout << root->val << " "; preorderTraversal(root->left); preorderTraversal(root->right); } ``` #### 前序非递归 ``` vector<int> preorderTraversal(TreeNode* root) { vector<int> result; if (root == NULL) return result; stack<TreeNode*> s; while (root != NULL || !s.empty()) { while (root != NULL) { result.push_back(root->val); s.push(root); root = root->left; } TreeNode* node = s.top(); s.pop(); root = node->right; } return result; } ``` #### 中序非递归 ``` vector<int> inorderTraversal(TreeNode* root) { vector<int> result; if (root == NULL) return result; stack<TreeNode*> s; while (root != NULL || !s.empty()) { while (root != NULL) { s.push(root); root = root->left; } TreeNode* node = s.top(); s.pop(); result.push_back(node->val); root = node->right; } return result; } ``` #### 后续非递归核心：根节点必须在右节点弹出之后，再弹出 ``` vector<int> postorderTraversal(TreeNode* root) { vector<int> result; if (root == NULL) return result; stack<TreeNode*> s; TreeNode* lastVisit; while (root != NULL || !s.empty()) { while (root != NULL) { s.push(root); root = root->left; } // 这里先看看，不弹出 TreeNode* node = s.top(); // 根节点必须在右节点弹出之后，再弹出 if (node->right == NULL || node->right == lastVisit) { s.pop(); result.push_back(node->val); lastVisit = node; } else root = node->right; } return result; } ``` ### DFS深度搜索-从上到下 ``` // 深度优先 void dfs(TreeNode* root, vector<int>& result) { if (root == NULL) return; result.push_back(root->val); dfs(root->left, result); dfs(root->right, result); } vector<int> preorderTraversal(TreeNode* root) { vector<int> result; dfs(root, result); return result; } ``` ### DFS深度搜索-从下到上（分治法） ``` vector<int> divideAndConquer(TreeNode* root) { vector<int> result; if (root == NULL) return result; // 分治 vector<int> left = divideAndConquer(root->left); vector<int> right = divideAndConquer(root->right); // 合并结果 result.push_back(root->val); result.insert(result.end(), left.begin(), left.end()); result.insert(result.end(), right.begin(), right.end()); return result; } vector<int> preorderTraversal(TreeNode* root) { return divideAndConquer(root); } ``` 注意点： `DFS深度搜索（从上到下）和分治法区别：前者一般将最终结果通过引用参数传入，或者一般递归返回结果最终合并` ### BFS层次遍历 ``` vector<int> levelTraversal(TreeNode* root) { vector<int> result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode *node = q.front(); q.pop(); result.push_back(node->val); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); } return result; } ``` ### 分治法应用先分别处理局部，再合并结果适用场景 * 快速排序 * 归并排序 * 二叉树相关问题 ## 常见题目示例 ### [104. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/) `给定一个二叉树，找出其最大深度` ``` class Solution { public: int maxDepth(TreeNode* root) { if (root == NULL) return 0; int left = maxDepth(root->left); int right = maxDepth(root->right); return (left > right ? left : right) + 1; } }; ``` #### [111\. 二叉树的最小深度](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/) 给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 **说明：**叶子节点是指没有子节点的节点。 ```cpp class Solution { public: int minDepth(TreeNode* root) { if (root == NULL) return 0; int left = minDepth(root->left); int right = minDepth(root->right); // 可能是叶子也可能是左右孩子为空 if (left == 0 || right == 0) return left + right + 1; // 左右孩子都不为空，返回最小深度 return min(left, right) + 1; } }; ``` ### [110. 平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/) `给定一个二叉树，判断它是否是高度平衡的二叉树` 思路：分治法，左边平衡&&右边平衡&&左右高度差<= 1，因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据，所以用-1表示不平衡，>=0表示数高度（二义性：一个变量有两个含义） ```cpp class Solution { public: bool isBalanced(TreeNode* root) { return maxLength(root) != -1; } /** * 可以在求最大深度时同时判断是否是平衡的 * 返回具有二义性，-1代表树不平衡 */ static int maxLength(TreeNode* root) { if (root == NULL) return 0; int left = maxLength(root->left); int right = maxLength(root->right); // -1 if (left == -1 || right == -1 || abs(left - right) > 1) return -1; return left > right ? left + 1 : right + 1; } }; ``` 注意 `一般工程中，结果通过两个变量来返回，不建议用一个变量表示两种含义` ### [124. 二叉树中的最大路径和](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/) `给定一个非空二叉树，返回其最大路径和` 思路：分治法，分三种情况：左子树最大路径和，右子树最大路径和，左右子树最大加根节点 ```cpp class Solution { public: int maxPathSum(TreeNode* root) { int result = INT_MIN; helper(root, result); return result; } int helper(TreeNode* root, int& result) { if (root == NULL) return 0; int left = max(helper(root->left, result), 0); //小于0就不考虑加上左子树上的点 int right = max(helper(root->right, result), 0); //同上 // 求的过程中考虑不包含当前节点父节点上面的节点 result = max(result, root->val + left + right); // 只返回包含当前根节点和左子树或者右子树的路径，返回上一层和result比较 return root->val + max(left, right); } }; ``` ### [236. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/) `给定一个二叉树, 找到该树中两个指定节点的最近公共祖先` 思路：两个节点 p,q 分为两种情况： * p 和 q 在相同子树中 * p 和 q 在不同子树中从根节点遍历，递归向左右子树查询节点信息递归终止条件：如果当前节点为空或等于 p 或 q，则返回当前节点 * 递归遍历左右子树，如果左右子树查到节点都不为空，则表明 p 和 q 分别在左右子树中，因此，当前节点即为最近公共祖先； * 如果左右子树其中一个不为空，则返回非空节点。 ```cpp class Solution { public: /** * 1. 若当前节点为空或者等于p或q，则直接返回当前节点 * 2. 若左右查到的节点都不为空，表明p和q分别在左右子树中，则返回的root就是公共祖先 * 3. 若左右查到的节点有一个不为空，则返回非空节点 */ TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL || 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; return left ? left : right; } }; ``` ### [102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/) `给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）` 思路：用一个队列记录一层的元素，然后扫描这一层元素并添加下一层元素到队列 ``` class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (root == NULL) return result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { vector<int> level; // 记录当前层有多少元素（遍历当前层，再添加下一层） int size = q.size(); for (int i = 0; i < size; i++) { TreeNode* node = q.front(); q.pop(); level.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } result.push_back(level); } return result; } }; ``` ### [107. 二叉树的层次遍历 II](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/) `给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）` 思路：在层级遍历的基础上，翻转一下结果即可 ``` class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> result; if (root == NULL) return result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { vector<int> level; // 记录当前层有多少元素（遍历当前层，再添加下一层） int size = q.size(); for (int i = 0; i < size; i++) { TreeNode* node = q.front(); q.pop(); level.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } result.push_back(level); } // 翻转 reverse(result.begin(), result.end()); return result; } }; ``` ### [103. 二叉树的锯齿形层次遍历](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/) `给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）` ```cpp class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> result; if (root == NULL) return result; queue<TreeNode*> q; q.push(root); bool needReverse = false; // 当前层是否需要翻转 while (!q.empty()) { vector<int> level; int size = q.size(); for (int i = 0; i < size; ++i) { TreeNode* node = q.front(); q.pop(); level.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } if (needReverse) reverse(level.begin(), level.end()); result.push_back(level); needReverse = !needReverse; } return result; } }; ``` ### [98. 验证二叉搜索树](https://leetcode-cn.com/problems/validate-binary-search-tree/) 给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征： * 节点的左子树只包含小于当前节点的数。 * 节点的右子树只包含大于当前节点的数。 * 所有左子树和右子树自身必须也是二叉搜索树。 ```cpp class Solution { public: bool isValidBST(TreeNode* root) { TreeNode* prev = NULL; return helper(root, prev); } bool helper(TreeNode* root, TreeNode*& prev) { if (root == NULL) return true; if (!helper(root->left, prev)) return false; if (prev && prev->val >= root->val) return false; prev = root; return helper(root->right, prev); } }; ``` ### [701. 二叉搜索树中的插入操作](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/) 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。思路：找到最后一个叶子节点满足插入条件即可 ```cpp class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == NULL) return new TreeNode(val); if (val < root->val) root->left = insertIntoBST(root->left, val); else root->right = insertIntoBST(root->right, val); return root; } }; ``` ### [剑指 Offer 27. 二叉树的镜像](https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/) ```cpp class Solution { public: /** * 思路：分别求左右子树的镜像，然后将左右子树交换 */ TreeNode* mirrorTree(TreeNode* root) { if (root == NULL) return root; TreeNode* left = mirrorTree(root->left); TreeNode* right = mirrorTree(root->right); root->left = right; root->right = left; return root; } }; ``` #### [剑指 Offer 36. 二叉搜索树与双向链表](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/) 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 ```cpp class Solution { public: Node* treeToDoublyList(Node* root) { if (root == NULL) return root; Node* prevNode = NULL; convertNode(root, prevNode); while (root->left) { root = root->left; } // 需要是循环链表，所以需要收尾连接上 root->left = prevNode; prevNode->right = root; return root; } void convertNode(Node* root, Node*& prevNode) { if (root == NULL) return; convertNode(root->left, prevNode); root->left = prevNode; if (prevNode) prevNode->right = root; prevNode = root; convertNode(root->right, prevNode); } }; ``` #### [剑指 Offer 26. 树的子结构](https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/) 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构，即 A中有出现和B相同的结构和节点值。例如: 给定的树 A: 3 / \ 4 5 / \ 1 2 给定的树 B： 4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。 ```cpp class Solution { public: bool isSubStructure(TreeNode* A, TreeNode* B) { bool result = false; if (A && B) { result = hasSubStructure(A, B); if (!result) result = isSubStructure(A->left, B); if (!result) result = isSubStructure(A->right, B); } return result; } bool hasSubStructure(TreeNode* A, TreeNode* B) { if (B == NULL) return true; if (A == NULL) return false; if (A->val != B->val) return false; return hasSubStructure(A->left, B->left) && hasSubStructure(A->right, B->right); } }; ``` #### [剑指 Offer 28. 对称的二叉树](https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/) 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 ```cpp class Solution { public: bool isSymmetric(TreeNode* root) { if (root == NULL) return true; return mirror(root->left, root->right); } bool mirror(TreeNode* A, TreeNode* B) { if (A == NULL && B == NULL) return true; if (A == NULL || B == NULL || A->val != B->val) return false; return mirror(A->left, B->right) && mirror(A->right, B->left); } }; ``` ## 总结 * 掌握二叉树递归与非递归遍历 * 理解DFS前序遍历与分治法 * 理解BFS层次遍历 ```cpp #include <iostream> #include <memory> #include <vector> #include <string.h> #include <map> #include <unordered_map> #include <list> #include <assert.h> #include <stack> #include <queue> using namespace std; // Definition for a binary tree node. struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { string result; queue<TreeNode *> q; q.push(root); while (!q.empty()) { TreeNode *n = q.front(); q.pop(); if (n == NULL) { result += "null,"; } else { result += to_string(n->val) + ","; q.push(n->left); q.push(n->right); } } result.pop_back(); return result; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { vector<string> nodes = getNodes(data); for (auto s : nodes) { cout << s << " "; } cout << endl; TreeNode *root = NULL; queue<TreeNode *> s; for (auto node : nodes) { TreeNode *newNode = NULL; if (node != "null") { newNode = new TreeNode(stoi(node)); } if (root == NULL) { root = newNode; } else { TreeNode *father = s.front(); if (father->left == NULL) { father->left = newNode; } else { father->right = newNode; s.pop(); } } if (newNode != NULL) { s.push(newNode); } } return root; } vector<string> getNodes(string data) { vector<string> result; while (data.find_first_of(',') != string::npos) { size_t pos = data.find_first_of(','); string node = data.substr(0, pos); data = data.substr(pos+1); result.push_back(node); } if (!data.empty()) result.push_back(data); return result; } }; /* 你可以序列化如下的二叉树 8 / \ 12 2 / \ 6 4 */ int main() { TreeNode *n1 = new TreeNode(8); TreeNode *n2 = new TreeNode(12); TreeNode *n3 = new TreeNode(2); TreeNode *n4 = new TreeNode(6); TreeNode *n5 = new TreeNode(4); n1->left = n2; n1->right = n3; n3->left = n4; n3->right = n5; Solution s; string result = s.serialize(n1); cout << result << endl; cout << "==========ddddd==========" << endl; TreeNode *newNode = s.deserialize(result); string str = s.serialize(newNode); cout << str << endl; return 0; } ```