二叉树的常见遍历以及面试题总结

发表于 | 更新于 | 评论数： | 阅读次数：

本文总结了二叉树的常见遍历方式，以及剪枝offer上的一些有关二叉树的面试题。

  1. 前序：中$\rightarrow$左$\rightarrow$右
  2. 中序：左$\rightarrow$中$\rightarrow$右
  3. 后序：左$\rightarrow$右$\rightarrow$中
  4. 层序遍历：第一层$\rightarrow$第二层$\rightarrow$第三层$\rightarrow$第n层（每层从做到右）

前序、中序、后序

树的遍历分递归实现与非递归实现：

  1. 递归实现：递归实现树的遍历，只需按照顺序依次递归即可，较为简单。
  2. 非递归实现：非递归实现需要用到STL容器，按照容器特性依次将树的节点放入容器中。
    1. stack容器：先进后出的特性
      • 先序遍历：应按右左的顺序将一个节点的子节点放入容器中，这样可保证左节点先于右节点取出。
      • 中序遍历：从根节点开始依次将节点的左节点放入栈，
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
//代码转载自https://blog.csdn.net/j_anson/article/details/49671523
/* 
二叉树实现 
*/  
#include<iostream>  
#include<string>  
#include<stack>  
#include<fstream>  
using namespace std;  
    
const int MAX_N = 100;  
//数据节点  
class Node  
{  
public:  
    char data;//数据  
    class Node *lchild;//左节点  
    class Node *rchild;//右节点  
};  
    
//二叉树  
class Tree  
{  
public:  
    Tree(){}  
    ~Tree(){}  
    
    //先序遍历非递归算法  
    void Disp()  
    {  
        if (t == NULL)  
        {  
            return;  
        }  
        stack<Node *> m_stack;  
        m_stack.push(t);  
        while (!m_stack.empty())  
        {  
            Node *p = m_stack.top();//赋值一份当前双亲节点  
            cout << p->data << ends;  
            m_stack.pop();  
            if (p->rchild)//先存储右子树，确保先输出左子树  
            {  
                m_stack.push(p->rchild);  
            }  
            if (p->lchild)//后存储左子树  
            {  
                m_stack.push(p->lchild);  
            }  
        }  
        
    }  
    
    //非递归中序遍历二叉树  
    void DispMid()  
    {  
        if (t == NULL)  
        {  
            return;  
        }  
        Node *p = t;  
        stack<Node *>m_stack;  
        while (p != NULL || !m_stack.empty())  
        {  
            while (p != NULL)//一路直走至左下角  
            {  
                m_stack.push(p);  
                p = p->lchild;  
            }  
            if (!m_stack.empty())  
            {  
                p = m_stack.top();//备份当前栈顶地址  
                m_stack.pop();  
                cout << p->data << ends;  
                p = p->rchild;  
            }  
        }  
    }  
    
    //非递归后序遍历二叉树  
    void DispBehid()  
    {  
        if (t == NULL)  
        {  
            return;  
        }  
        Node *pre = NULL, *p = t;  
        stack<Node *>m_stack;  
        while (p != NULL || !m_stack.empty())  
        {  
            while (p != NULL)//一路直走至左下角  
            {  
                m_stack.push(p);  
                p = p->lchild;  
            }  
            p = m_stack.top();  
            //右子树为空或者已访问，输出当前节点  
            if (p->rchild == NULL || p->rchild == pre)  
            {  
                cout << p->data << ends;  
                pre = p;//将当前结点地址赋值pre作为下一次判断标志，防止重复访问  
                m_stack.pop();  
                p = NULL;//p赋值空以便访问右子树  
            }  
            else  
            {  
                p = p->rchild;//访问子树的右子树  
            }  
        }  
    }  
    //构建二叉树  
    void Create(string name)  
    {  
        ifstream readfile;  
        string str;  
        readfile.open(name);  
        if (readfile.is_open())  
        {  
            getline(readfile, str);//读取一行  
        }  
        readfile.close();  
        CreateNode(str);//构建二叉树  
    }  
    
    //递归先序遍历输出二叉树  
    void display()  
    {  
        cout << "Output:";  
        output(t);  
        cout << endl;  
    }  
    
    //递归中序遍历输出二叉树  
    void displayMid()  
    {  
        cout << "Output:";  
        outputMid(t);  
        cout << endl;  
    }  
    
    //递归后序遍历输出二叉树  
    void displayBhind()  
    {  
        cout << "output:";  
        outputBhind(t);  
        cout << endl;  
    }  
    //二叉树高度  
    void Height()  
    {  
        int height = get_height(t);  
        cout << "Height: " << height << endl;  
    }  
    
    //输出叶子节点值  
    void display_leaf()  
    {  
        cout << "Leaves: ";  
        output_leaf(t);  
        cout << endl;  
    }  
private:  
    Node *t;  
    
    //构建二叉树  
    void CreateNode(string str)  
    {  
        stack<Node *> m_stack;  
        Node *p;  
        int k;  
        while (str.length() != 0)  
        {  
            //若当前为'('，将双亲节点推入栈，下一位存储的p值作为左节点处理  
            if (str[0] == '(')  
            {  
                m_stack.push(p); k = 1;  
            }  
            //为右括号则栈顶退出一位  
            else if (str[0] == ')')  
            {  
                m_stack.pop();  
            }  
            //为','，则下一个字符作右节点处理  
            else if (str[0] == ',')  
            {  
                k = 2;  
            }  
            //存储值用作双亲结点  
            else  
            {  
                p = (Node *)malloc(sizeof(Node));  
                p->data = str[0];  
                p->lchild = p->rchild = NULL;  
                //树根为空时，将第一个节点作为树根并赋值给私有成员变量  
                if (t == NULL)  
                {  
                    t = p;  
                }  
                //树根不为空  
                else  
                {  
                    if (k == 1)//作为左节点处理，将栈中双亲节点的左指针指向当前节点  
                    {  
                        m_stack.top()->lchild = p;  
                    }  
                    else//作为右节点处理  
                    {  
                        m_stack.top()->rchild = p;  
                    }  
                }  
            }  
            //重构串，除去首字符，并将串长度减小1  
            str.assign(str.substr(1, str.length() - 1));  
        }  
    }  
    
    //递归先序遍历输出二叉树  
    void output(Node *t)  
    {  
        if (t != NULL)//当树根不为空时  
        {  
            cout << t->data;//输出  
            if (t->lchild != NULL || t->rchild != NULL)//左/右结点不为空时递归到下一层  
            {  
                cout << "(";  
                output(t->lchild);  
                if (t->rchild != NULL)//当左节点遍历结束后，左节点递归返回一层，递归右节点  
                {  
                    cout << ",";  
                }  
                output(t->rchild);  
                cout << ")";  
            }  
        }  
    }  
    
    //递归中序遍历二叉树  
    void outputMid(Node *t)  
    {  
        if (t == NULL)  
        {  
            return;  
        }  
        else  
        {  
            cout << "(";  
            outputMid(t->lchild);  
            if (t->rchild != NULL)  
            {  
                cout << ",";  
            }  
            cout << t->data;  
            outputMid(t->rchild);  
            cout << ")";  
        }  
    }  
    
    //递归后序遍历输出二叉树  
    void outputBhind(Node *t)  
    {  
        if (!t)  
        {  
            return;  
        }  
        else  
        {  
            cout << "(";  
            outputBhind(t->lchild);  
            if (t->rchild != NULL)  
            {  
                cout << ",";  
            }  
            outputBhind(t->rchild);  
            cout << t->data;  
            cout << ")";  
        }  
    }  
    //求树高  
    int get_height(Node *t)  
    {  
        int leftheight, rightheight;  
        if (t == NULL)//递归至不存在子节点时返回0  
        {  
            return 0;  
        }  
        else  
        {  
            leftheight = get_height(t->lchild);//递归求左子树高度  
            rightheight = get_height(t->rchild);//递归其右子树高度  
            return leftheight > rightheight ? leftheight+1 : rightheight+1;//递归返回时返回最大值  
        }  
    }  
    
    //查找左节点  
    Node *leftchild(Node *p)  
    {  
        return p->lchild;  
    }  
    
    //查找右节点  
    Node *rightchild(Node *p)  
    {  
        return p->rchild;  
    }  
    
    //输出叶子节点  
    void output_leaf(Node *t)  
    {  
        if (t != NULL)//树根不为空时  
        {  
            //当前节点没有子节点时输出节点数据  
            if (t->lchild == NULL&&t->rchild == NULL)  
            {  
                cout << t->data << ends;  
            }  
            output_leaf(t->lchild);//递归左子树  
            output_leaf(t->rchild);//递归右子树  
        }  
    }  
};  
    
    
int main()  
{  
    Tree m_tree;  
    m_tree.Create("data");  
    m_tree.display();//递归先序输出  
    m_tree.displayMid();//递归中序输出  
    m_tree.displayBhind();//递归后序输出  
    m_tree.Height();//树高  
    m_tree.display_leaf();//叶子节点  
    m_tree.Disp();//非递归先序遍历  
    cout << endl;  
    m_tree.DispMid();//非递归中序遍历  
    cout << endl;  
    m_tree.DispBehid();//非递归后序遍历  
    cout << endl;  
    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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//代码转载自https://blog.csdn.net/FX677588/article/details/74276513
#include<cstdio>
#include<queue>
using namespace std;
/*二叉树结构体，并且构建了有参构造函数*/
struct BinaryTree{
    int vec;
    BinaryTree* left;
    BinaryTree* right;
    BinaryTree(int data)
        :vec(data), left(nullptr), right(nullptr){ 
    }
};
/*队列实现层序遍历*/
void printTree(BinaryTree* arr[])
{
    queue<BinaryTree*> rel; //定义一个队列，数据类型是二叉树指针，不要仅是int！！不然无法遍历
    rel.push(arr[0]);
    while (!rel.empty())
    {
        BinaryTree* front = rel.front();
        printf("%d\n", front->vec);
        rel.pop();                  //删除最前面的节点
        if (front->left != nullptr) //判断最前面的左节点是否为空，不是则放入队列
            rel.push(front->left);  
        if (front->right != nullptr)//判断最前面的右节点是否为空，不是则放入队列
            rel.push(front->right);
    }
}
int main(){
    /*构建二叉树*/
    BinaryTree* s_arr[6];
    s_arr[0] = new BinaryTree(0);
    s_arr[1] = new BinaryTree(1);
    s_arr[2] = new BinaryTree(2);
    s_arr[3] = new BinaryTree(3);
    s_arr[4] = new BinaryTree(4);
    s_arr[5] = new BinaryTree(5);
    s_arr[0]->left = s_arr[1];  //   0
    s_arr[0]->right = s_arr[2]; //  1  2
    s_arr[1]->left = s_arr[3];  // 3     5
    s_arr[3]->left = s_arr[4];  //4
    s_arr[2]->right = s_arr[5]; //所以层序遍历的结果为：0 1 2 3 5 4
    /*层次遍历打印所有节点*/
    printTree(s_arr);
    /*释放所有空间*/
    for (int i = 0; i < 6; i++)
        delete s_arr[i];
    return 0;
}

剑指offer树遍历题目整理

二叉树的下一个节点

  • 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
  • 中序遍历：左中右,因此给定节点左子树已经遍历完全，下一个节点存在2中情况：
    1. 存在右子树：对右子树进行中序遍历
    2. 不存在右子树：此种情况下又分几种情况：
      1. 该节点为父节点的左子树：则父节点的左子树已经完全遍历，下一个应该遍历其父节点
      2. 该节点为父节点的右子树：父节点已经完全遍历，继续搜索父节点的父节点。
      3. 父节点不存在（即该节点为根节点）：输出系欸但右子树。
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
/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        TreeLinkNode* pHead=pNode;
        if(!pHead) return NULL;
        if(pHead->right) {
            TreeLinkNode* res=pHead->right;
            while(res->left) res=res->left;
            return res;
        }
        else if(pHead->next){
            while(pHead->next){
                if(pHead->next->left==pHead)
                    return pHead->next;
                else
                    pHead=pHead->next;
            }
            return NULL;
        }
        return NULL;
    }
};

对称二叉树

  • 题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
  • 依次对比吧。感觉我很喜欢写递归，对非递归方式不是很熟，接下来几题还是非递归方式联系一下。
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
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(!pRoot||(!pRoot->left&&!pRoot->right)) return true;
        return node2(pRoot->left,pRoot->right);
    }
    bool node2(TreeNode* n1,TreeNode* n2){
        if((!n1^!n2)) return false;
        if((n1&&n2)&&n1->val!=n2->val){
            return false;
        }
        else if(!n1&&!n2)return true;
        return node2(n1->left,n2->right)&&node2(n2->left,n1->right);
    }
};

从上到下打印二叉树

  • 题目描述：从上往下打印出二叉树的每个节点，同层节点从左至右打印。
  • 层序遍历，这道题是刚开始刷题的时候写的，现在看起来写的都是什么鬼，反正能AC，放这把。
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
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<int> print_vec;
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<TreeNode*> node_pre,node;
        if(root==NULL)return print_vec;
        if(root->left!=NULL)
            node.push_back(root->left);
        if(root->right!=NULL)
            node.push_back(root->right);
        print_vec.push_back(root->val);
        while(!node.empty())
        {
            for(auto i=0;i<node.size();i++)
            {
                print_vec.push_back(node[i]->val);
            }
            vector<TreeNode*> x;
            node_pre.swap(node);
            x.swap(node);
            for (auto i=0;i<node_pre.size();i++)
            {
                if(node_pre[i]->left!=NULL)
                    node.push_back(node_pre[i]->left);
                if(node_pre[i]->right!=NULL)
                    node.push_back(node_pre[i]->right);
            }
        }
        return print_vec;
    }
};

把二叉树打印成多行

  • 题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
  • 使用队列层序遍历，难点在于如何判别是否进入下一层，分析可知，队列中只存在2层的节点，遍历上一层时将下一层节点加入队列中，本例中使用一个指针layer指向一层的最后一个节点（queue.back()），当这一层打印完时，临界状态为队列中仅存在上一层的最后一个节点与下一层的所有节点，此时，layer==queue.front()，更新layer=queue.back()，即可进入下一层的迭代。评论里也有使用queue.size()记录每层的长度的，思路其实一样。
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
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            queue<TreeNode *> node;
            node.push(pRoot);
            vector<vector<int> >res;
            TreeNode* p=pRoot,*layer=pRoot;
            if(!pRoot) return res;
            while(!node.empty()){
                vector<int> n;
                do{
                    p=node.front();
                    node.pop();
                    if(p->left) node.push(p->left);
                    if(p->right) node.push(p->right);
                    n.push_back(p->val);
                }while(layer!=p&&!node.empty());
                if(!node.empty())layer=node.back();
                res.push_back(n);
            }
            return res;
        }
};

之字形打印二叉树

  • 题目描述：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
  • 和上题类似，使用双端队列保存节点，加入一个记录行数的变量。也可使用2个队列，一个记录奇数行，一个记录偶数行。后者在上题的基础上，得到顺序打印的res，再将res的偶数行反转。
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
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        deque<TreeNode *> node;
        node.push_back(pRoot);
        vector<vector<int> >res;
        TreeNode* p=pRoot,*layer=pRoot;
        int counts=1;
        if(!pRoot) return res;
        while(!node.empty()){
            vector<int> n;
            if(counts%2==1){
                do{
                    p=node.front();
                    node.pop_front();
                    if(p->left) node.push_back(p->left);
                    if(p->right) node.push_back(p->right);
                    n.push_back(p->val);
                }while(layer!=p&&!node.empty());
                if(!node.empty())layer=node.front();
            }
            else{
                do{
                    p=node.back();
                    node.pop_back();
                    if(p->right) node.push_front(p->right);
                    if(p->left) node.push_front(p->left);
                    n.push_back(p->val);
                }while(layer!=p&&!node.empty()); 
                if(!node.empty())layer=node.back();
            }
            res.push_back(n);
            counts+=1;
        }
        return res;
    }
};

二叉树的镜像

  • 题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    二叉树的镜像定义：源二叉树 
        	    8
        	   /  \
        	  6   10
        	 / \  / \
        	5  7 9 11
        	镜像二叉树
        	    8
        	   /  \
        	  10   6
        	 / \  / \
        	11 9 7  5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot==NULL||(pRoot->left==NULL && pRoot->right==NULL))return;
        TreeNode *pLeft=pRoot->left;
        TreeNode *pRight=pRoot->right;
        pRoot->left=pRight;
        pRoot->right=pLeft;
        Mirror(pRight);
        Mirror(pLeft);
    }
};

二叉树的第k个节点

  • 题目描述:给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
  • 这题找了好久的bug，无语了，还是对中序遍历不是太熟悉的缘故。其实也就是在中序遍历加上一个计数器而已。
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
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        stack<TreeNode*> que;
        if(!pRoot) return pRoot;
        TreeNode* p=pRoot;
        int n=1;
        do{
            while(p){
                que.push(p);
                p=p->left;
            }
            if(n==k) goto end;
            n++;
            if(!que.empty()){
                p=que.top();
                p=p->right;
                que.pop();
            }
        }while(!que.empty()||p);
        end:
        if(que.empty())
            return NULL;
        return que.top();
    }
};

二叉树中的某一路径

  • 题目描述：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
  • 习惯新地就写了个递归版本，注意判断节点是否叶子节点
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
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > res;
        vector<int> n;
        if(!root) return res;
        finder(root,expectNumber,res,n);
        return res;
    }
    void finder(TreeNode* root,int expectNumber,vector<vector<int> > &res,vector<int> &n){
        if(!root||root->val>expectNumber||(root->val==expectNumber&&(root->left||root->right))) return;
        else if(root->val==expectNumber&&(!root->left&&!root->right)){
            n.push_back(root->val);
            res.push_back(n);
            n.pop_back();
            return;
        }
        n.push_back(root->val);
        finder(root->left,expectNumber-root->val,res,n);
        finder(root->right,expectNumber-root->val,res,n);
        n.pop_back();
    }
};
//链接：https://www.nowcoder.com/questionTerminal/b736e784e3e34731af99065031301bca
//非递归版本
//思路：
/*
1.按先序遍历把当前节点cur的左孩子依次入栈同时保存当前节点，每次更新当前路径的和sum；
2.判断当前节点是否是叶子节点以及sum是否等于expectNumber，如果是，把当前路径放入结果中。
3.遇到叶子节点cur更新为NULL，此时看栈顶元素，如果栈顶元素的把栈顶元素保存在last变量中，同时弹出栈顶元素，当期路径中栈顶元素弹出，sum减掉栈顶元素，这一步骤不更改cur的值；
4.如果步骤3中的栈顶元素的右孩子存在且右孩子之前没有遍历过，当前节点cur更新为栈顶的右孩子，此时改变cur=NULL的情况。
*/
#include <iostream>
#include <vector>
 
using namespace std;
 
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL){}
}
 
vector<vector<int> > FindPath(TreeNode *root, int expectNumber){
    vector<vector<int> > res;   
    if (root == NULL)
        return res;
    stack<TreeNode *> s;
    s.push(root);
    int sum = 0; //当前和
    vector<int> curPath; //当前路径
    TreeNode *cur = root; //当前节点
    TreeNode *last = NULL; //保存上一个节点
    while (!s.empty()){
        if (cur == NULL){
            TreeNode *temp = s.top();
            if (temp->right != NULL && temp->right != last){
                cur = temp->right; //转向未遍历过的右子树
            }else{
                last = temp; //保存上一个已遍历的节点
                s.pop();
                curPath.pop_back(); //从当前路径删除
                sum -= temp->val;
            }  }
        else{
            s.push(cur);
            sum += cur->val;
            curPath.push_back(cur->val);
            if (cur->left == NULL && cur->right == NULL && sum == expectNum){
                res.push_back(curPath);
            }
            cur = cur->left; //先序遍历，左子树先于右子树
        }
    }
    return res;
}

二叉搜索树地后序遍历结果

  • 题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
  • 这题开始没有一点思路，后来想了想后续遍历地特点才知道怎么写，后续遍历地遍历顺序是：左右中，因此数组最末尾就是树的根节点，前面一段分别是左子树、右子树，而左子树的末尾是左子树的根节点，右子树的末尾是右子树的根节点，因此可以递归求解了。如下图所示：

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
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int len=sequence.size();
        if(len<1) return false;
        return judger(sequence,0,len-1);
    }
    bool judger(vector<int> &sequence,int left,int right){
        if(left==right) return true;
        int root=sequence[right];
        int mid=left-1;
        for(int i=left;i<right;i++){
            if(sequence[i]<root)
                mid=i;
            else
                break;
        }
        for(int i=mid+1;i<right;i++){
            if(sequence[i]<root)
                return false;
        }
        if(mid==left-1)
            return judger(sequence,mid+1,right-1);
        else if(mid==right-1)
            return judger(sequence,left,mid);
        return judger(sequence,left,mid)&&judger(sequence,mid+1,right-1);
    }
};

树的子结构

  • 题目描述:输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
  • 这题没做出来，我想着在原函数上递归，后来一直超时，应该用一个新的函数的。
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
//链接：https://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88
//来源：牛客网
/*思路：参考剑指offer
1、首先设置标志位result = false，因为一旦匹配成功result就设为true，
剩下的代码不会执行，如果匹配不成功，默认返回false
2、递归思想，如果根节点相同则递归调用DoesTree1HaveTree2（），
如果根节点不相同，则判断tree1的左子树和tree2是否相同，
再判断右子树和tree2是否相同
3、注意null的条件，HasSubTree中，如果两棵树都不为空才进行判断，
DoesTree1HasTree2中，如果Tree2为空，则说明第二棵树遍历完了，即匹配成功，
tree1为空有两种情况（1）如果tree1为空&&tree2不为空说明不匹配，
（2）如果tree1为空，tree2为空，说明匹配。
 
*/
 
class Solution {
    bool isSubtree(TreeNode* pRootA, TreeNode* pRootB) {
        if (pRootB == NULL) return true;
        if (pRootA == NULL) return false;
        if (pRootB->val == pRootA->val) {
            return isSubtree(pRootA->left, pRootB->left)
                && isSubtree(pRootA->right, pRootB->right);
        } else return false;
    }
public:
    bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB)
    {
        if (pRootA == NULL || pRootB == NULL) return false;
        return isSubtree(pRootA, pRootB) ||
            HasSubtree(pRootA->left, pRootB) ||
            HasSubtree(pRootA->right, pRootB);
    }
};

重建二叉树

  • 题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
  • 依据前序与中序遍历的性质，前序为中左右，中序为左中右，根据前序数组的第一个节点为根节点，在中序数组中找到该节点位置，则左边为左子树，右边为右子树，递归生成整棵树。
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
/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
            int inlen=in.size();
            if(inlen==0)
                return NULL;
            vector<int> left_pre,right_pre,left_in,right_in;
            //创建根节点，根节点肯定是前序遍历的第一个数
            TreeNode* head=new TreeNode(pre[0]);
            //找到中序遍历根节点所在位置,存放于变量gen中
            int gen=0;
            for(int i=0;i<inlen;i++)
            {
                if (in[i]==pre[0])
                {
                    gen=i;
                    break;
                }
            }
            //对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边
            //利用上述这点，对二叉树节点进行归并
            for(int i=0;i<gen;i++)
            {
                left_in.push_back(in[i]);
                left_pre.push_back(pre[i+1]);//前序第一个为根节点
            }
            for(int i=gen+1;i<inlen;i++)
            {
                right_in.push_back(in[i]);
                right_pre.push_back(pre[i]);
            }
            //和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树
            //递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
           head->left=reConstructBinaryTree(left_pre,left_in);
           head->right=reConstructBinaryTree(right_pre,right_in);
           return head;
        }
    };

本文标题:二叉树的常见遍历以及面试题总结

文章作者:微石

发布时间:2018年06月15日 - 09:06

最后更新:2018年07月19日 - 17:07

原始链接:akihoo.github.io/posts/47f04b2c.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。