首页 > 代码库 > 我要好offer之 二叉树大总结
我要好offer之 二叉树大总结
一. 二叉树定义：二叉树具有天然的递归特性，凡是二叉树相关题，首先应该联想到递归
struct BinTreeNode { BinTreeNode* left; BinTreeNode* right; int val; BinTreeNode(int value) : left(nullptr), right(nullptr), val(value) { }};
二. 二叉树遍历
详见笔者博文：二叉树遍历大总结
1 #include <iostream> 2 #include <vector> 3 #include <stack> 4 using namespace std; 5 6 // 二叉树递归定义 7 struct BinTreeNode { 8 BinTreeNode* left; 9 BinTreeNode* right; 10 int val; 11 BinTreeNode(int value) : left(NULL), right(NULL), val(value) { } 12 }; 13 14 // 根据结点值构建二叉树 15 BinTreeNode* BuildBinTree(BinTreeNode* root, int value) { 16 if (root == NULL) { 17 root = new BinTreeNode(value); // 结点为空，new一个节点 18 } else if (value <= root->val) { 19 root->left = BuildBinTree(root->left, value); 20 } else { 21 root->right = BuildBinTree(root->right, value); 22 } 23 return root; 24 } 25 26 // 先序遍历，递归 27 void PreOrder(BinTreeNode* root) { 28 if (root == NULL) return; 29 std::cout << root->val << "-->"; // 访问节点 30 PreOrder(root->left); 31 PreOrder(root->right); 32 } 33 34 // 先序遍历，非递归，栈版本 35 void PreOrderStk(BinTreeNode* root) { 36 if (root == NULL) return; 37 std::stack<BinTreeNode*> stk; 38 while (root != NULL || !stk.empty()) { 39 while (root != NULL) { 40 std::cout << root->val << "-->"; // 访问节点 41 stk.push(root); 42 root = root->left; // 深度优先搜索到最左节点，然后回溯 43 } 44 BinTreeNode* cur = stk.top(); 45 stk.pop(); 46 root = cur->right; // 转向右子树 47 } 48 } 49 50 // 先序遍历，非递归，非栈，Morris 51 void PreOrderMorris(BinTreeNode* root) { 52 if (root == NULL) return; 53 BinTreeNode* prev = NULL; // prev为刚刚访问过的节点 54 BinTreeNode* cur = root; // cur为正在访问的结点 55 while (cur != NULL) { 56 if (cur->left == NULL) { 57 std::cout << cur->val << "-->"; // 访问节点 58 prev = cur; // 更新刚刚访问过的结点 59 cur = cur->right; 60 } else { 61 BinTreeNode* node = cur->left; // 前驱结点为 左子树最右下节点 62 while (node->right != NULL && node->right != cur) { 63 node = node->right; 64 } 65 if (node->right == NULL) { // 还没线索化，则建立线索 66 std::cout << cur->val << "-->"; // 仅这一行与中序不同 67 node->right = cur; // 建立线索 68 prev = cur; // 更新刚刚访问过的结点 69 cur = cur->left; 70 } else { 71 cur = cur->right; 72 node->right = NULL; // 已经线索化，则删除线索 73 } 74 } 75 } 76 } 77 78 // 中序遍历，递归 79 void InOrder(BinTreeNode* root) { 80 if (root == NULL) return; 81 InOrder(root->left); 82 std::cout << root->val << "-->"; // 访问节点 83 InOrder(root->right); 84 } 85 86 // 中序遍历，非递归，栈版本 87 void InOrderStk(BinTreeNode* root) { 88 if (root == NULL) return; 89 std::stack<BinTreeNode*> stk; 90 while (root != NULL || !stk.empty()) { 91 while (root != NULL) { 92 stk.push(root); 93 root = root->left; // 深度优先搜索到最左节点，然后回溯 94 } 95 BinTreeNode* cur = stk.top(); 96 stk.pop(); 97 std::cout << cur->val << "-->"; // 访问节点 98 root = cur->right; // 转向右子树 99 }100 }101 102 // 中序遍历，非递归，非栈，Morris103 void InOrderMorris(BinTreeNode* root) {104 if (root == NULL) return;105 BinTreeNode* prev = NULL; // prev为刚刚访问过的结点106 BinTreeNode* cur = root; // cur为正在访问的结点107 while (cur != NULL) {108 if (cur->left == NULL) {109 std::cout << cur->val << "-->"; // 访问节点110 prev = cur; // 更新刚刚访问过的结点111 cur = cur->right;112 } else {113 BinTreeNode* node = cur->left; // 前驱结点为 左子树最右下节点114 while (node->right != NULL && node->right != cur) {115 node = node->right;116 }117 if (node->right == NULL) { // 还没线索化，则建立线索118 node->right = cur; // 建立线索119 cur = cur->left;120 } else {121 std::cout << cur->val << "-->"; // 已经线索化，则访问节点，并删除线索122 prev = cur;123 cur = cur->right;124 node->right = NULL; // 删除线索125 }126 }127 }128 }129 130 // 后序遍历，递归131 void PostOrder(BinTreeNode* root) {132 if (root == NULL) return;133 PostOrder(root->left);134 PostOrder(root->right);135 std::cout << root->val << "-->";136 }137 138 // 后序遍历，非递归，栈版本139 void PostOrderStk(BinTreeNode* root) {140 if (root == NULL) return;141 std::stack<BinTreeNode*> stk;142 BinTreeNode* cur = root;143 BinTreeNode* prev = NULL;144 do {145 while (cur != NULL) {146 stk.push(cur);147 cur = cur->left;148 }149 prev = NULL;150 while (!stk.empty()) {151 cur = stk.top();152 stk.pop();153 if (cur->right == prev) {154 std::cout << cur->val << "-->";155 prev = cur;156 } else {157 stk.push(cur);158 cur = cur->right;159 break;160 }161 }162 } while (!stk.empty());163 }164 165 // 层次遍历，递归版166 void LevelOrder(BinTreeNode* root, int level, std::vector<std::vector<int>>& res) {167 if (root == NULL) return;168 if (level > res.size()) {169 res.push_back(std::vector<int>());170 }171 res.at(level - 1).push_back(root->val);172 LevelOrder(root->left, level + 1, res);173 LevelOrder(root->right, level + 1, res);174 }175 std::vector<std::vector<int>> LevelOrderHelp(BinTreeNode* root) {176 std::vector<std::vector<int>> res;177 LevelOrder(root, 1, res);178 return res;179 }180 181 // 层次遍历，非递归，队列版182 void LevelOrderQueue(BinTreeNode* root) {183 if (root == NULL) return;184 std::deque<BinTreeNode*> dequeTreeNode;185 dequeTreeNode.push_back(root);186 while (!dequeTreeNode.empty()) {187 BinTreeNode* cur = dequeTreeNode.front();188 dequeTreeNode.pop_front();189 std::cout << cur->val << "-->"; // 访问节点190 if (cur->left != NULL) dequeTreeNode.push_back(cur->left);191 if (cur->right != NULL) dequeTreeNode.push_back(cur->right);192 }193 }194 195 int main() {196 // your code goes here197 std::vector<int> num = {6, 2, 7, 1, 4, 9, 3, 5, 8};198 BinTreeNode* root = nullptr;199 for (auto val : num) {200 root = BuildBinTree(root, val);201 }202 std::cout << "1:PreOrder:" << std::endl;203 std::cout << "\t PreOrder:" ; 204 PreOrder(root);205 std::cout << std::endl;206 std::cout << "\t PreOrderStk:"; 207 PreOrderStk(root); 208 std::cout << std::endl;209 std::cout << "\t PreOrderMorris:"; 210 PreOrderMorris(root); 211 std::cout << std::endl;212 213 std::cout << "2:InOrder:" << std::endl;214 std::cout << "\t InOrder:";215 InOrder(root); 216 std::cout << std::endl;217 std::cout << "\t InOrderStk:";218 InOrderStk(root); 219 std::cout << std::endl;220 std::cout << "\t InOrderMorris:";221 InOrderMorris(root);222 std::cout << std::endl;223 224 std::cout << "3:PostOrder:" << std::endl;225 std::cout << "\t PostOrder:";226 PostOrder(root);227 std::cout << std::endl;228 std::cout << "\t PostOrderStk:";229 PostOrderStk(root);230 std::cout << std::endl;231 232 std::cout << "4:LevelOrder:" << std::endl;233 std::cout << "\t LevelOrder:";234 LevelOrderQueue(root); 235 std::cout << std::endl;236 return 0;237 }
三. 二叉树构建
1. 先序序列和中序序列构建一颗二叉树 中序序列和后序序列构建一棵二叉树
2. 有序数组/链表 构建一颗二叉查找树BST
四. 二叉树判断
1. 判断二叉查找树BST
2. 判断平衡二叉树
3. 判断对称二叉树
4. 判断相同二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。