shaoyuanhangyes

shaoyuanhangyes@outlook.com

Binary-Tree

发表于 更新于 分类于

Binary-Tree

本篇文章为shaoyuanhangyes.github.io/二叉树的重置版本
更新了部分代码 更改了排版 舍弃了冗杂的赘述内容 利用STL容器进行了更新

二叉树

![二叉树example](B.png)

二叉树结构体

1
2
3
4
5
6
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(NULL),right(NULL) {}
};

二叉树的创建

采用的是更为直观的层序遍历的方式 将二叉树和对应数组序号的元素一一填入

1
2
3
4
5
6
7
8
9
10
//以层序的方式创建二叉树 len为数组长度 index为元素位置序号
TreeNode* createTree(const vector<int> &nums,int len,int index){
    TreeNode *root=NULL;
    if(index<len&&nums[index]!=-1){//值为null和位置不合法时直接返回空节点
        root = new TreeNode(nums[index]);
        root->left = createTree(nums,len,2*index+1);
        root->right= createTree(nums,len,2*index+2);
    }
    return root;
}

二叉树的遍历

二叉树的遍历中 层序遍历属于广度优先(BFS) 前中后序遍历都属于深度优先(DFS)

层序遍历

利用队列进行迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//层序遍历 利用队列进行迭代 返回的是一个二维vector数组 因此需要一个函数来打印这个vector数组
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if(!root) return res;
    queue<TreeNode* > Tree;
    Tree.push(root);
    while(!Tree.empty()){
        vector<int> temp;
        int len=Tree.size();
        while(len--){
            TreeNode *pNode=Tree.front();
            Tree.pop();
            temp.push_back(pNode->val);
            if(pNode->left) Tree.push(pNode->left);
            if(pNode->right) Tree.push(pNode->right);
        }
        res.push_back(temp);
    }
    return res;
}

打印二维数组的代码为

1
2
3
4
5
6
7
8
9
10
//打印二维数组
void PrintMartrix(vector<vector<int>>& res){
    for(int i=0;i<res.size();++i){
        cout<<"[";
        for(int j=0;j<res[i].size();++j){
            cout<<" "<<res[i][j]<<" ";
        }
        cout<<"]"<<endl;
    }
}

先序遍历

遍历顺序为 根 左 右

1
2
3
4
5
6
7
//先序遍历递归算法 遍历到就直接cout输出
void preOrder(TreeNode *root){
    if(!root) return;
    cout<<root->val<<" ";
    preOrder(root->left);
    preOrder(root->right);
}

中序遍历

遍历顺序为 左 根 右

1
2
3
4
5
6
7
//中序遍历递归算法
void inOrder(TreeNode *root){
    if(!root) return;
    inOrder(root->left);
    cout<<root->val<<" ";
    inOrder(root->right);
}

后序遍历

遍历顺序为 左 右 根

1
2
3
4
5
6
7
//后序遍历递归算法
void postOrder(TreeNode *root){
    if(!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->val<<" ";
}

全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(NULL),right(NULL) {}
};
//以层序的方式创建二叉树 len为数组长度 index为元素位置序号
TreeNode* createTree(const vector<int> &nums,int len,int index){
    TreeNode *root=NULL;
    if(index<len&&nums[index]!=-1){//值为null和位置不合法时直接返回空节点
        root = new TreeNode(nums[index]);
        root->left = createTree(nums,len,2*index+1);
        root->right= createTree(nums,len,2*index+2);
    }
    return root;
}
//打印二维数组
void PrintMartrix(vector<vector<int>>& res){
    for(int i=0;i<res.size();++i){
        cout<<"[";
        for(int j=0;j<res[i].size();++j){
            cout<<" "<<res[i][j]<<" ";
        }
        cout<<"]"<<endl;
    }
}
//层序遍历 利用队列进行迭代
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if(!root) return res;
    queue<TreeNode* > Tree;
    Tree.push(root);
    while(!Tree.empty()){
        vector<int> temp;
        int len=Tree.size();
        while(len--){
            TreeNode *pNode=Tree.front();
            Tree.pop();
            temp.push_back(pNode->val);
            if(pNode->left) Tree.push(pNode->left);
            if(pNode->right) Tree.push(pNode->right);
        }
        res.push_back(temp);
    }
    return res;
}
//先序遍历递归算法
void preOrder(TreeNode *root){
    if(!root) return;
    cout<<root->val<<" ";
    preOrder(root->left);
    preOrder(root->right);
}
//中序遍历递归算法
void inOrder(TreeNode *root){
    if(!root) return;
    inOrder(root->left);
    cout<<root->val<<" ";
    inOrder(root->right);
}
//后序遍历递归算法
void postOrder(TreeNode *root){
    if(!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->val<<" ";
}

int main(){
    vector<int> nums={0,1,2,3,4,5,6,7,8,-1,10};//示例 -1代表所在位置为空值
    int len=nums.size();
    TreeNode *root=createTree(nums,len,0);
    cout<<"层序遍历的二维数组序列为: "<<endl;
    vector<vector<int>> res=levelOrder(root);
    PrintMartrix(res);
    cout<<endl<<"先序遍历序列为: ";
    preOrder(root);
    cout<<endl<<"中序遍历序列为: ";
    inOrder(root);
    cout<<endl<<"后序遍历序列为: ";
    postOrder(root);
    return 0;
}

程序输出结果为

1
2
3
4
5
6
7
8
9
10
11
层序遍历的二维数组序列为:
[ 0 ]
[ 1  2 ]
[ 3  4  5  6 ]
[ 7  8  10 ]

先序遍历序列为: 0 1 3 7 8 4 10 2 5 6
中序遍历序列为: 7 3 8 1 4 10 0 5 2 6
后序遍历序列为: 7 8 3 10 4 1 5 6 2 0
Process finished with exit code 0

二叉树进阶

更多进阶的算法以及刷题解答见shaoyuanhangyes/LeetCode/树

二叉树刷题C++模版

1
2
3
4
5
6
7
8
9

/*二叉树结构体*/
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(NULL),right(NULL) {}
};

创建二叉树

因为二叉树是非线性结构 不易于直接表示 因此采取顺序存储的思想 按照数组的序号对这个数组以层序遍历的方式创建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

TreeNode* createTree(const vector<int> &nums,int len,int index){
    TreeNode *root=NULL;
    if(index<len&&nums[index]!=-1){//值为null和位置不合法时直接返回空节点
        root = new TreeNode(nums[index]);
        root->left = createTree(nums,len,2*index+1);
        root->right= createTree(nums,len,2*index+2);
    }
    return root;
}
int main(){
    vector<int> nums={0,1,2,3,4,5,6,7,8,-1,10};//示例 -1代表所在位置为空值
    int len=nums.size();
    TreeNode *root=createTree(nums,len,0);
    return 0;
}

创建后的二叉树为

1
2
3
4
5
6
7
8
9

        0
      /   \
    1       2
   / \     / \
  3   4   5   6
 / \   \
7   8   10

二叉树的遍历们

前序遍历

前序遍历(先序遍历) 遍历的次序为 根 左 右 

1
2
3
4
5
6
7
8
9
10
11

        0
      /   \
    1       2
   / \     / \
  3   4   5   6
 / \   \
7   8   10      为例子

前序遍历的序列为 [0 1 3 7 8 4 10 2 5 6]

前序遍历序列的第一个节点一定是二叉树的根节点

前序遍历递归代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

vector<int> res;//必须是全局变量的数组
vector<int> preorderTraversal(TreeNode* root) {
    if(root!=NULL){
        res.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
    return res;
}
int main(){
    vector<int> nums={0,1,2,3,4,5,6,7,8,-1,10};//示例 -1代表所在位置为空值
    int len=nums.size();
    TreeNode *root=createTree(nums,len,0);
    cout<<"先序遍历的序列为:"<<endl
    vector<int> preOrder=preOrderTraversal(root);
    for(auto x:preOrder) cout<<x<<" ";
    return 0;
}

前序遍历迭代代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

vector<int> preorderTraversal(TreeNode* root) {
	vector<int> res;
	stack<TreeNode* > st;
	TreeNode* node=root;
	while(!st.empty()||node){
	    while(node){
	        st.push(node);
	        res.push_back(node->val);
	        node=node->left;
	    }
	    node=st.top();
	    st.pop();
	    node=node->right;
	}
	return res;
}
int main(){
    vector<int> nums={0,1,2,3,4,5,6,7,8,-1,10};//示例 -1代表所在位置为空值
    int len=nums.size();
    TreeNode *root=createTree(nums,len,0);
    cout<<"先序遍历的序列为:"<<endl
    vector<int> preOrder=preOrderTraversal(root);
    for(auto x:preOrder) cout<<x<<" ";
    return 0;
}

中序遍历

中序遍历 遍历的次序为 左 根 右 

1
2
3
4
5
6
7
8
9
10
11

        0
      /   \
    1       2
   / \     / \
  3   4   5   6
 / \   \
7   8   10      为例子

中序遍历的序列为 [7 3 8 1 4 10 0 5 2 6]

通过前序遍历确定了二叉树的根节点后 在中序遍历序列中 根节点的左半部分都是根节点的左子树 根节点的右半部分都是根节点的右子树
BST 二叉搜索树 又名二叉排序树 二叉查找树 的中序序列一定是按从小到大的顺序排列的

中序遍历递归代码
1
2
3
4
5
6
7
8
9
10
11
12
13

vector<int> res;//必须是全局变量的数组
vector<int> inorderTraversal(TreeNode* root) {
    if(root!=NULL){
        inorderTraversal(root->left);
        res.push_back(root->val);
        inorderTraversal(root->right);
    }
    return res;
}

/*以下的主函数不赘述了*/

中序遍历迭代代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

vector<int> inorderTraversal(TreeNode* root) {//迭代算法
    vector<int> res;
    stack<TreeNode *> st;
    TreeNode *node=root;
    while(!st.empty()||node){
        while(node){
            st.push(node);
            node=node->left;
        }
        node=st.top();
        st.pop();
        res.push_back(node->val);
        node=node->right;
    }
    return res;
}

后序遍历

后序遍历 遍历的次序为 左 右 根

1
2
3
4
5
6
7
8
9
10
11

        0
      /   \
    1       2
   / \     / \
  3   4   5   6
 / \   \
7   8   10      为例子

后序遍历的序列为 [7 8 3 10 4 1 5 6 2 0]

后序遍历序列的最后一个节点一定是根节点

后序遍历递归代码
1
2
3
4
5
6
7
8
9
10
11

vector<int> res;
vector<int> postorderTraversal(TreeNode* root){
    if(root!=NULL){
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        res.push_back(root->val);
    }
    return res;
}

后序遍历迭代代码

第一种解法 标记位

prev记录已经输出到res数组中的上一个节点 防止出现某一节点有右孩子 右孩子输出后 根据栈回到右孩子的父节点 然后又判断是否有右孩子的死循环 当判断到node->right==prev成立 即父节点的右孩子上一次被访问过 就输出这个父节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

vector<int> postorderTraversal(TreeNode* root){
    vector<int> res;
    stack<TreeNode* > st;
    TreeNode* node=root;
    TreeNode* prev=NULL;
    while(!st.empty()||node){
        while(node){
            st.push(node);
            node=node->left;
        }
        node=st.top();
        if(node->right==NULL||node->right==prev){
            res.push_back(node->val);
            st.pop();
            prev=node;
            node=NULL;
        }
        else node=node->right;
    }
    return res;
}

第二种解法 反转

根据前序遍历的思想 将遍历序列规则转换为 根 右 左 序列输出到数组后 将整个数组反转过来 就变成了左 右 根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

vector<int> preorderTraversal(TreeNode* root) {
	vector<int> res;
	stack<TreeNode* > st;
	TreeNode* node=root;
	while(!st.empty()||node){
	    while(node){
	        st.push(node);
	        res.push_back(node->val);//根
	        node=node->right;//右
	    }
	    node=st.top();
	    st.pop();
	    node=node->left;//左
	}
	reverse(res.begin(),res.end());//#include <algorithm>
	return res;
}

层序遍历

层序遍历 每一层元素 按从左到右的顺序逐层输出 

1
2
3
4
5
6
7
8
9
10
        0
      /   \
    1       2
   / \     / \
  3   4   5   6
 / \   \
7   8   10      为例子

层序遍历的序列为 [0 1 2 3 4 5 6 7 8 10]

层序遍历迭代算法

利用队列进行迭代 返回二维数组 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if(!root) return res;
    queue<TreeNode* > Tree;
    Tree.push(root);
    while(!Tree.empty()){
        vector<int> temp;
        int len=Tree.size();
        while(len--){
            TreeNode *pNode=Tree.front();
            Tree.pop();
            temp.push_back(pNode->val);
            if(pNode->left) Tree.push(pNode->left);
            if(pNode->right) Tree.push(pNode->right);
        }
        res.push_back(temp);
    }
    return res;
}

打印二维数组的方法

1
2
3
4
5
6
7
8
9
10
11

void PrintMartrix(vector<vector<int>>& res){
    for(int i=0;i<res.size();++i){
        cout<<"[";
        for(int j=0;j<res[i].size();++j){
            cout<<" "<<res[i][j]<<" ";
        }
        cout<<"]"<<endl;
    }
}

Binary Search Tree

二叉搜索树 又被翻译为二叉排序树 二叉查找树

特点具体为 每个节点的值 大于其任意左侧子节点的值 小于其任意右侧子节点的值

BST插入

给定二叉搜索树（BST）的根节点和要插入树中的值 将值插入二叉搜索树 返回插入后二叉搜索树的根节点 保证原始二叉搜索树中不存在新值

注意 可能存在多种有效的插入方式 只要树在插入后仍保持为二叉搜索树即可 你可以返回任意有效的结果

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
例如, 

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和 插入的值: 5
你可以返回这个二叉搜索树:

         4
       /   \
      2     7
     / \   /
    1   3 5
或者这个树也是有效的:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

递归解法

1
2
3
4
5
6
7
8
9
10
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);
        if(val>root->val) root->right=insertIntoBST(root->right,val);
        return root;
    }
};

复杂度分析
  1. 时间复杂度: O(H) H为Tree的高度 平均情况log2N 最坏情况O(N)
  2. 空间复杂度: 平均情况下O(H) 最坏情况O(N) 是在递归过程中堆栈使用的空间

复杂度中最坏的情况就是二叉树高度为二叉树节点数量的时候 即

1
2
3
4
5
6
7
      5
     /   
    2     
   /   
  1  
 /
4

要插入的元素需要遍历到最深才能插入

迭代解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode* insertIntoBST(TreeNode* root,int val){
        TreeNode* node=root;
        while(node!=NULL){
            if(val>node->val){
                if(node->right==NULL){
                    node->right=new TreeNode(val);
                    return root;
                }
                else node=node->right;
            }
            else{
                if(node->left==NULL){
                    node->left=new TreeNode(val);
                    return root;
                }
                else node=node->left;
            }
        }
        return new TreeNode(val);
    }
复杂度分析
  1. 时间复杂度: O(H) H为Tree的高度 平均情况log2N 最坏情况O(N)
  2. 空间复杂度: O(1)
End of reading! -- Thanks for your supporting