以下是數(shù)據(jù)結(jié)構(gòu)部分的主要知識點的思維導圖
tree_introduce.png
在這段時間基本上刷的都是跟二叉樹有關(guān)的題目九默，所以下面主要針對二叉樹部分進行總結(jié)逃魄。
二叉樹的各種操作基本上離不開基本的幾個點，遍歷伍俘、搜索癌瘾、節(jié)點插入和刪除饵溅。利用這幾個操作互相結(jié)合就能解決大部分問題，當然前提是先理解它們的意義和熟悉操作代碼的編寫咬荷。下面分別對這些操作進行代碼的實現(xiàn)與分析轻掩。
二叉樹操作.png
假設(shè)樹的結(jié)構(gòu)體實現(xiàn)如下：
Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
遍歷 （前序唇牧、中序、后序）
以中序遍歷為例(其他兩種情況大同小異)腔召，假設(shè)現(xiàn)在需要對一個根節(jié)點為root(不為空)的樹進行遍歷將節(jié)點的值按順序放到vector中扮惦，這種情況下同常有遞歸和非遞歸兩種實現(xiàn)方式，實現(xiàn)代碼如下：
- 遞歸實現(xiàn)
class Solution {
public:
vector<int> traverse(TreeNode* root, vector<int>& vec) {
traverse(root->left);
vec.push_back(root->val);
traverse(root->right);
return vec;
}
};
- 使用棧實現(xiàn)h
1.遍歷后樹會發(fā)生變化的實現(xiàn)方式
class Solution {
public:
vector<int> traverse(TreeNode* root, vector<int>& vec) {
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* node = s.top();
if(node ->left){
s.push(node ->left);
node ->left = NULL;//防止重復遍歷
}else{
s.pop();
vec->push(node->val);
if(node->right){
s.push(node->right);
}
}
}
}
return vec;
}
};
2.遍歷后原樹不會發(fā)生變化(使用unordered_map)
class Solution {
public:
vector<int> traverse(TreeNode* root, vector<int>& vec) {
unordered_map<TreeNode*, bool> map;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* node = s.top();
if(node ->left && !map[node]){
s.push(node ->left);
map[node->left] = true;
}else{
s.pop();
vec->push(node->val);
if(node->right){
s.push(node->right);
}
}
}
}
return vec;
}
};
3.遍歷后原樹不會發(fā)生變化(不使用unordered_map)
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> vector;
stack<TreeNode *> stack;
TreeNode *pCurrent = root;
while(!stack.empty() || pCurrent)
{
if(pCurrent)
{
//同一根節(jié)點下的左右節(jié)點客峭，左節(jié)點比右節(jié)點先出棧（即左節(jié)點后進棧,其實最后所有進棧的節(jié)點都可以視左一個樹中的中間節(jié)點氧卧。）
stack.push(pCurrent);
pCurrent = pCurrent->left;//若左節(jié)點為空則沙绝，該節(jié)點可以等同為中間節(jié)點，相對于其右節(jié)點先出棧（后進棧）
}//節(jié)點為空就出棧
else
{//當左子節(jié)點或右子節(jié)點沒有左子節(jié)點時 改節(jié)點出棧
TreeNode *pNode = stack.top();
vector.push_back(pNode->val);
stack.pop();
pCurrent = pNode->right;
}
}
return vector;
}
};
由于篇幅所限前序遍歷和后序遍歷的代碼就不貼了星著，可去這個地方查看：
https://github.com/kid1943/leetcode/tree/master/tree/Binary%20Tree%20Preorder%20Traversal
https://github.com/kid1943/leetcode/tree/master/tree/Binary%20Tree%20Postorder%20Traversal
逐層遍歷
- 自上而下
class Solution {
public:
vector<int> traverse(TreeNode* root) {
queue<TreeNode*> q;
queue<int> level;
q.push(root);
level.push(0);
vector<int> vec;
int m = -1;
int result;
while(q.size()){
TreeNode* sr = q.front();
result = sr->val;
int l = level.front();
level.pop();
q.pop();
if(sr->left){
q.push(sr->left);
level.push(l+1);
}
if(sr->right){
q.push(sr->right);
level.push(l+1);
}
}
return level;
}
};
節(jié)點的刪除
要刪除二叉搜索樹中的某個節(jié)點p需要考慮三種情況：
1）p有兩顆非空子樹
2）p是樹葉
3）p是只有一顆非空子樹
刪除p節(jié)點的思路
1）要刪除的節(jié)點p具有兩顆非空子樹虚循。先將該節(jié)點的元素替換為它的左子樹的最大元素或右子樹的最小元素样傍。
2）要刪除的節(jié)點是葉子節(jié)點 。處理的方法是釋放該節(jié)點空間茎刚，若是根節(jié)點撤逢，則令根為NULL。
3 ) 要刪除的節(jié)點p只有一顆子樹初狰。如果p沒有節(jié)點(即p是根節(jié)點)互例，則p的唯一子樹的根節(jié)點成為新的搜索樹的根節(jié)點。如果p有父節(jié)點pp俊马，則修改pp的指針域肩杈，使得它指向p的唯一孩子，然后釋放節(jié)點p扩然。
- 以下是我實現(xiàn)的代碼
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
root = deleteNodeitem(root, key);
return root;
}
TreeNode* deleteNodeitem(TreeNode* root, int key){
TreeNode* p = root;//the keynode to delete
TreeNode* pp = root;//parentNode of the keynode
TreeNode* s;//the node to replace the keynode
TreeNode* ps;//parent node of replacenode
//findout the keynode p and its parant node pp
while((p != NULL)&&(p->val != key)){
pp = p;
if(key > p->val){
p = p->right;
}else if(key < p->val){
p = p->left;
}
}
//can not find the keynode
if(p == NULL){
return root;
}
//state1 node p have 2 nonull childnode
if((p->left!=NULL)&&(p->right!=NULL)){
//find the biggest node in the right tree
s = p->right;
ps = p;
while(s->left != NULL){
ps = s;
s = s->left;
}
//初始化一個要替換刪除節(jié)點的節(jié)點
TreeNode q = {s->val};
q.left = p->left;
q.right = p->right;
//將刪除節(jié)點指向新構(gòu)造出來的節(jié)點q
if(pp->left == p){
pp->left = &q;
}else if(pp->right == p){
pp->right = &q;
}else if(p == root){//要刪除的節(jié)點就是根節(jié)點
pp->val = q.val;
}
//make the s node to delete 找出節(jié)點s所對應的父節(jié)點
if(ps != p){
pp = ps;
}else if((p == ps)&&(p!=root)){//當s的父節(jié)點即為p節(jié)點時
pp = &q;
}
p = s;//it must one left child of p if p has child
}
//statue2 node p have at most one nonull childnode
//在只有一個非空子樹的情況下界睁，只需要將刪除子樹的非空子樹將其替換就可以了
TreeNode* pc = p;//the child of p , if it has.
if(p->left != NULL){
pc = p->left;
}else if(p->right != NULL){
pc = p->right;
}else{
pc = NULL;//p has no child
}
if(pp->left == p){
pp->left = pc;
}else if(pp->right == p){
pp->right = pc;
}else{
root = pc;//根節(jié)點就是需要刪除的節(jié)點
}
return root;
}
};
- 利用遞歸
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (root->val == key) {
if (!root->right) {
TreeNode* left = root->left;
delete root;
return left;
}
else {
TreeNode* right = root->right;
//找出右子樹的最小節(jié)點
while (right->left)
right = right->left;
swap(root->val, right->val);
}
}
//利用遞歸找出左右子樹中要刪除的節(jié)點翻斟，
//并利用該節(jié)點的右子樹中的左子樹的最小節(jié)點替換掉要被刪除的節(jié)點
root->left = deleteNode(root->left, key);
root->right = deleteNode(root->right, key);
return root;
}
};
題目思路整理
- Find Bottom Left Tree Value 逐層遍歷
- Find Largest Value in Each Tree Row 逐層遍歷或前序遍歷
- Find Largest Value in Each Tree Row 利用中序遍歷可以得到由小到大的集合
- Maximum Depth of Binary Tree 后序遍歷或逐層遍歷
- Most Frequent Subtree Sum 中序遍歷，計算每個節(jié)點的值及其左右子樹的值之和
- Invert Binary Tree 后序遍歷
- Binary Tree Tilt 后序遍歷求和
- Sum of Left Leaves 前序遍歷嘹履，找出左子葉
- Same Tree 后序或前序遍歷節(jié)點進行比較
- Binary Tree Inorder Traversal 中序遍歷的實現(xiàn)
未完待續(xù)
