Point2OfferCode/36_Tree_Convert_List.cpp at master · slientreed/Point2OfferCode · GitHub

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

//
//  Created by mark on 2019/7/17.
//  Copyright © 2019年 mark. All rights reserved.
//

/*
 说明：
 1. 问题：36.二叉搜索树和双向链表。把二叉搜索树转化成双向链表
 2. 思路：分成左子树，root，右子树。然后递归

 */


#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <assert.h>

using namespace std;


struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};


void ConvertNodeRecursive(TreeNode* root, TreeNode** pLastNode);


TreeNode* Convert(TreeNode* pRootOfTree)
{
    if(pRootOfTree == nullptr)
        return NULL;

    TreeNode* pLastNode = nullptr;                 // 指向已经排序树已经转换好的节点,指向双向链表的尾节点
    ConvertNodeRecursive(pRootOfTree, &pLastNode);     // 递归转换节点

    TreeNode* pHeadList = pLastNode;                    // 返回双向链表的头结点,从尾节点，一直遍历到头结点返回
    while(pHeadList != nullptr && pHeadList->left != nullptr)
        pHeadList = pHeadList->left;

    return pHeadList;

}

void ConvertNodeRecursive(TreeNode* root, TreeNode** pLastNode)
{
    if(root == nullptr)
        return;

    TreeNode* pCur = root;

    if(pCur->left != nullptr)                           // 中序遍历，先递归左子树
        ConvertNodeRecursive(pCur->left, pLastNode);

    pCur->left = *pLastNode;                        // 当前根节点的左指针，指向已经完成转换的最后一个节点;
    if(*pLastNode != nullptr)
        (*pLastNode)->right = pCur;

    *pLastNode = pCur;                         // 更新已经完成排序的最后一个节点

    if(pCur->right != nullptr)                //  递归转换右子树
        ConvertNodeRecursive(pCur->right, pLastNode);
}


int main(){

    //    4
    //  3
    //2

    TreeNode tree[3];  // 建3个节点
    tree[0].val = 4;
    tree[0].left = &tree[1];
    tree[0].right = NULL;
    tree[1].val = 3;
    tree[1].left = &tree[2];
    tree[1].right = NULL;
    tree[2].val = 2;
    tree[2].left = NULL;
    tree[2].right = NULL;

    TreeNode* p = Convert(tree);

    while(p != nullptr)
    {
        cout << "当前节点：" << p->val << " ";
        if(p->left != nullptr)
            cout << "左节点：" << p->left->val << " ";
        if(p->right != nullptr)
            cout << "右节点：" << p->right->val << " ";
        cout << endl;
        p = p->right;
    }

    cout << endl;

    return 0;
}