Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

Posted on Edited on In Valine:

二叉树的序列化与反序列化-题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。

您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。

样例
你可以序列化如下的二叉树
8
/ \
12 2
/ \
6 4

为：”[8, 12, 2, null, null, 6, 4, null, null, null, null]”
注意:

以上的格式是AcWing序列化二叉树的方式，你不必一定按照此格式，所以可以设计出一些新的构造方式

中二叉树的序列化与反序列化-总体思路

重点考虑反序列化，我们需要考虑一种很容易找到root节点的遍历方式。

如果我无法找到root节点，是无法通过递归来完成反序列化的。

在前中后三种遍历中，我们可以选择先序遍历。 先序遍历，最容易找到root节点

中二叉树的序列化与反序列化-代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string s;
    
    void dfs_s(TreeNode* root, string& res) {
        if (!root) {
            res += "null ";
            return;
        }
        
        res += (to_string(root->val) + " ");
        dfs_s(root->left, res);
        dfs_s(root->right, res);
    }
    
    
    //1, 2, 4, 5, 6, null, null, null
    // 注意此处是引用类型
    // 如果不用下标，直接用字符串char*呢？ 他应该是char*& ,而不可以是char* 
    // char* 是指针，但是确是值传递！！对于值传递，当递归到内部时，外层无法感知到内部变化；
    TreeNode* dfs_us(int& u) {
        if (u >= s.size()) {
            return NULL;
        }
        
        //如果是nullptr
        if (s[u] == 'n') {
            u += 5;
            return nullptr;
        }
        
        //如果是有意义的内容
        int val = 0;
        int flag = 1;
        if (s[u] == '-') {flag = -1; u++;}
        while (s[u] != ' ') {
            val = val * 10 + s[u++] - '0';
        }
        val *= flag;
        u++;
        
        //上面都是处理当前节点
        
        auto r = new TreeNode(val);
        auto left = dfs_us(u); //处理左边
        auto right = dfs_us(u);
        r->left =left, r->right = right;
        return r;
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        dfs_s(root, res);
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        s = data;
        int c = 0;
        return dfs_us(c);
    }
};

Posted on Edited on In Valine:

获取不同的翻译方法次数-题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：

0翻译成”a”，1翻译成”b”，……，11翻译成”l”，……，25翻译成”z”。

一个数字可能有多个翻译。例如12258有5种不同的翻译，它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

样例
输入：”12258”

输出：5

获取不同的翻译方法次数-总体思路

首先最容易想到的解法是递归，但是我们注意到有很多重复计算，所以更优的做法应该是DP

dp[i]表示0到s[i]这个字符串能够包含的翻译方法。

启发式思考：对于字符串类的DP问题，dp[i]一般是表示以i为结尾的字符串要计算的值。

d[i] = dp[i - 1] + dp[i - 2] when as a ALHPA OR dp[i - 1] when other

获取不同的翻译方法次数-代码实现

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
class Solution {
public:
    string s;
    
    int dfs(int u) {
        int res = 0;
        if (u == s.size()) {
            return 1;
        }
        
        res += (1 * dfs(u + 1)); //长度为1的结果数量
        if (u + 1 < s.size()) {
           int val = 10 * (s[u] - '0') + s[u + 1] - '0';
           if (10 <= val && val <= 25) { 
               res += (1 * dfs(u + 2)); //长度为2的结果数
           }
        }
        
        return res;
    }
    
    int getTranslationCount(string _s) {
        s = _s;
        return dfs(0);
    }
};

Posted on Edited on In , Valine:

复制复杂链表-题目描述

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

函数结束后原链表要与输入时保持一致。

复制复杂链表-总体思路

有两种思路：

第一种思路，比较容易想到

（1）遍历一遍，复制出新的node, 并维护好node之间的next关系，同时使用HashMap存储新旧node的映射关系

（2）再遍历一遍，借助hashMap找到新节点对应的random指向过去。

时间复杂度：$O(2n)$, 空间复杂度：$O(n)$

那么我们是否可以不使用额外的空间吗？答案是可以的（此处需要启发式思考，实在想不出我觉得也问题不大！）

（1）遍历一遍，复制新的节点，作为原节点的下一个节点插入到链表中

（2）遍历一遍，如果有random指针，则借助新插入的节点找到新的random指针目标节点

（3）再遍历一遍，访问链表，去掉老的链表节点

时间复杂度：$O(3n)$, 空间复杂度：$O(1)$

复制复杂链表-代码实现

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
/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        if (!head) return NULL;
        
        for (auto p = head; p;) {
            auto np = new ListNode(p->val);
            auto next = p->next;
            np->next = next;
            p->next = np;
            p = next;
        }
    
        for (auto p = head; p; p = p->next->next) {
            if (p->random) {
                p->next->random = p->random->next;
            }
        }
        
        auto dummy = new ListNode(-1);
        auto tail = dummy;
        
        for (auto p =head; p;) {
            tail = tail->next = p->next;
            p = p->next = p->next->next;
        }
        
        
        return dummy->next;
    }
};

Posted on Edited on In Valine:

检查合法Stack的弹出序列-题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。

样例
输入：[1,2,3,4,5]
[4,5,3,2,1]

输出：true

检查合法Stack的弹出序列-总体思路

模拟一遍；

对于每一个pushed序列元素，

对于栈有两个操作：
（1）当前元素入栈
（2）弹出栈。

如果弹出序列的当前元素与栈顶元素相同，则弹出；否则继续入栈。

首先压入第一个元素；

然后紧接着此时栈有两个操作？ 弹出当前元素 或者 继续压入新的元素。

如何区分呢？

要看top与弹出序列的当前是否一致；如果一致，说明弹出了元素； 如果不一致，说明压入了新的元素。

接着再继续比较…

检查合法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
class Solution {
public:
/*
[1,2,3,5]
1,2,3, 5, 
q: [4,5,3,1,2]

*/
bool isPopOrder(vector<int> p,vector<int> q) {
        if (p.size() != q.size()) return false;
        stack<int> s;
        int i = 0, j = 0;
        while (j < int(q.size())) {
            if (s.empty() || s.top() != q[j]) {
                if (i == int(p.size())) {
                    return false;
                }
                s.push(p[i++]);
            }
            else {
                s.pop();
                j++;
            }
        }
        return true;
    }
};

Posted on Edited on In Valine:

如果我们把二叉树视为一个图，父子节点之间的连线视为双向的，我们姑且定义为“举例”为两节点之间边的个数。写一个程序求一颗二叉树中相距最远的两个节点之间的距离（《编程之美》3.8）

解题思路

该题目的技巧在于 全局变量的 应用。

需要克服的惯性思维：更多的题目的计算结果会作为递归函数的返回变量。

这个函数的返回值其实是root节点的高度。

在计算高度的过程中，顺便完成全局变量的更新。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int GetMaxDistance(TreeNode* root) {
    if (root == NULL) return 0;
    
    int max_distance = INT_MIN;

    dfs(root, INT_MIN);

    return max_distance
}

int dfs(TreeNode* root, int &max_distance) {
    if (root == NULL) return -1;

    int left_max_depth = dfs(root->left, &max_distance);
    int right_max_depth = dfs(root->right, &max_distance);

    int temp_distance = left_max_depth + right_max_depth + 2;

    if (temp_distance > max_distance) max_distance = temp_distance;

    return left_max_depth > right_max_depth ? left_max_depth + 1 : right_max_depth + 1;
}

Posted on Edited on In Valine:

二叉树中结点值的和为输入整数的所有路径-题目描述

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

样例
给出二叉树如下所示，并给出num=22。
5
/ \
4 6
/ / \
12 13 6
/ \ / \
9 1 5 1

输出：[[5,4,12,1],[5,6,6,5]]

二叉树中结点值的和为输入整数的所有路径-总体思路

这里，我在下面的代码中写了很多种写法，我们需要好好体会以下几个点：

（1）我的return条件是什么？（是遇到空节点return还是遇到叶子结点return)

（2）我应该如何处理当前访问到的节点

（2）我应该如何还原现场（是pop一次还是pop两次）

（3）return条件与还原现场的关系是什么？

二叉树中结点值的和为输入整数的所有路径-代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    
    //一种写法【正确】---如果到达空节点，则返回
    void dfs(TreeNode* root, int sum) {
        if (!root) return;
        
        path.push_back(root->val);
        sum -= root->val;
        if (!root->left && !root->right && !sum) {
            res.push_back(path);
            //这里不会return;
            //假设最后一个叶子结点是一个错误答案，我们显然需要把这个节点pop出来？
            //那我pop的时机是什么呢？ 显然是在遍历完左右子树之后再pop出来。
        }
       
        dfs(root->left, sum);
        dfs(root->right, sum);
        path.pop_back();
    }
    
    //一种正确的写法：注意这里，非叶子节点才会被push进去，所以只需要pop一次；
    void dfs(TreeNode* root, int sum) {
        //结束条件
        if (!root->left && !root->right) { 
            if (sum == root->val) {
                path.push_back(root->val);
                ret.push_back(path);
                path.pop_back();
            }
            return;
        }

        path.push_back(root->val);
        if (root->left) dfs(root->left, sum - root->val);
        if (root->right) dfs(root->right, sum- root->val);
        path.pop_back();
    }


    //另一种正确的写法---如果到达叶子节点，则返回
     void dfs2(TreeNode* root, int sum) {
        path.push_back(root->val);
        sum -= root->val;
        if (!root->left && !root->right) {
            if (!sum) {
                res.push_back(path);
            }  
            return; //注意这里有一个return
            //注意这里return了，现在path中有一个错误的节点，我这个节点需要什么时候pop出来呢？
            //显然只能在外层调用的时候。
        }
       
        if (root->left) {
            dfs(root->left, sum);
            path.pop_back();
        }

        if (root->right) {
            dfs(root->right, sum);
            path.pop_back();
        }
    }

     //错误的写法---如果到达叶子节点，则返回; 但是只pop了一次！！！
     void dfs3(TreeNode* root, int sum) {
        path.push_back(root->val);
        sum -= root->val;
        if (!root->left && !root->right) {
            if (!sum) {
                res.push_back(path);
            } 
            return;  //注意这里有一个return
        }
       
        if (root->left) {
            dfs(root->left, sum);
        }

        if (root->right) {
            dfs(root->right, sum);
        }

        path.pop_back();
    }
    
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        dfs(root, sum);
        return res;
    }
};

Posted on Edited on In , Valine:

中序遍历序列的下一个节点-题目描述

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

如果给定的节点是中序遍历序列的最后一个，则返回空节点;
二叉树一定不为空，且给定的节点一定不是空节点；
样例
假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。

则应返回值等于3的节点。

解释：该二叉树的结构如下，2的后继节点是3。
2
/ \
1 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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        //如果有右孩子，则一直遍历找到其左左左..
        if (p->right) {
            p = p->right;
            while (p->left) p = p->left;
            return p;
        }
        
        //判断他自己是左孩子，还是右孩子。
        //如果是左孩子，则直接访问其父亲
        //如果是右孩子，则一直访问，直到不是右孩子。
        
        while (p->father && p->father->left != p) p = p->father;
        return p->father;
    }
};

Posted on Edited on In Valine:

从上往下打印出二叉树，同层从左到右-题目描述

从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。

样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
8
/ \
12 2
/
6
/
4

输出：[8, 12, 2, 6, 4]

从上往下打印出二叉树，同层从左到右-总体思路

借助queue来实现层次遍历

从上往下打印出二叉树，同层从左到右-代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
 
    vector<int> printFromTopToBottom(TreeNode* root) {
         vector<int> res;
        queue<TreeNode*> q;
    
        if (!root) return res;
        
        q.push(root);
        while (!q.empty()) {
            auto r = q.front();
            q.pop();
            res.push_back(r->val);
            if (r->left) q.push(r->left);
            if (r->right) q.push(r->right); 
        }
        
        return res;
    }
    
};

从上往下打印出二叉树，同层从左到右，分行打印-题目描述

从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。

样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
8
/ \
12 2
/
6
/
4

输出：[[8], [12, 2], [6], [4]]

从上往下打印出二叉树，同层从左到右，分行打印-总体思路

相对上题，难点在于如何识别分行，一般而言我们有以下几种办法：

（1）使用nullptr作为分隔符，每次遇到nullptr进行分行处理，并压入新的nullptr。nullptr是当前层的终止符。

（2）借助size, 每次遍历size个元素，size为上一次压入的元素个数。通过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
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        
        if (!root) return res;
        
        q.push(root);
        q.push(nullptr);
        vector<int> level;
        
        while (q.size()) {
            auto t = q.front();
            q.pop();
            
            if (!t) {
                if (level.empty()) break;
                res.push_back(level);
                level.clear();
                q.push(nullptr);
                continue;
            }
            
            level.push_back(t->val);
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
            
        }
    }

     vector<vector<int>> printFromTopToBottom2(TreeNode* root) {
        vector<vector<int>> res;
        vector<int> level;
        queue<TreeNode*> q;
        
        if (!root) return res;
        q.push(root);
        while (q.size()) {
            int qs = q.size();  //必须赋值到局部变量
            for (int i = 0; i < qs; ++i) {
                auto t = q.front();
                q.pop();
                level.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            res.push_back(level);
            level.clear();   
        }
    }
};

从上往下打印出二叉树，同层从左到右，之字形打印-题目描述

请实现一个函数按照之字形顺序从上向下打印二叉树。

即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]
8
/ \
12 2
/ \
6 4
输出：[[8], [2, 12], [6, 4]]

从上往下打印出二叉树，同层从左到右，之字形打印-总体思路

基于上题，在res加入元素之前，判定res是否奇数，如果是奇数的话，就reverse一下子level数组

从上往下打印出二叉树，同层从左到右，之字形打印-代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        
        if (!root) return res;
        
        q.push(root);
        q.push(nullptr);
        vector<int> level;
        
        bool flag = false;
        
        while (q.size()) {
            auto t = q.front();
            q.pop();
            
            if (!t) {
                if (level.empty()) break;
                if (flag) reverse(level.begin(), level.end());
                res.push_back(level);
                level.clear();
                q.push(nullptr);
                flag = !flag;
                continue;
            }
            
            level.push_back(t->val);
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
            
        }
    }

    vector<vector<int>> printFromTopToBottom2(TreeNode* root) {
        vector<vector<int>> res;
        vector<int> level;
        queue<TreeNode*> q;
        
        if (!root) return res;
        q.push(root);
        while (q.size()) {
            int qs = q.size();
            for (int i = 0; i < qs; ++i) {
                auto t = q.front();
                q.pop();
                level.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            if (res.size() % 2) {
                reverse(level.begin(), level.end());
            }
            res.push_back(level);
            level.clear();   
        }
    }
};

垂直打印二叉树

解答思路：

  1. 依旧是通过层次打印
  2. 放入队列的不仅是tree node， 还需要放入当前的横向坐标
  3. root坐标为0， 左节点减1， 右节点加1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef std::pair<int, TreeNode*> PIT;

class Solution {
public:
    vector<vector<int>> printV(TreeNode* root) {
        unsorted_map<int, vector<int>&> m;
        queue<PIT> q;

        q.push_back(make_pair(0, root));
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                PIT p = q.top(); q.pop();
                m[p.first].push_back(p.second.val);
                if (p.second->left)
                    q.push_back(make_pair(p.first - 1, p.second->left));
                if (p.second->right)
                    q.push_back(make_pair(p.first - 1, p.second->right));
            }
        }
    }

};

Posted on Edited on In , Valine:

二叉搜索树转有序双向链表-题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

注意：

需要返回双向链表最左侧的节点。
例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。

二叉搜索树转有序双向链表-总体思路

两种思路：

第一种思路，dfs的主要任务是返回子树对应链表的头尾节点；按照这种思路的话，我们的遍历方式是后序遍历。

第二种思路，dfs的主要任务就是按照顺序访问到每一个node，同时记录一个全局的pre，然后将pre与node建立双向关联即可。

二叉搜索树转有序双向链表-代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
pair<Node*, Node*> dfs(Node* root) {
    if (!(root->left) && !(root->right)) {
        root->left = root;
        root->right = root;
        return {root, root};
    }
    
    //访问左边
    pair<Node*, Node*>  left = {root, root};
    if (root->left) {
        left = dfs(root->left);
    }

    //访问右边
    pair<Node*, Node*>  right = {root, root};
    
    if (root->right) {
        right = dfs(root->right);
    }

    //访问中间节点
    if (left.first != root) {
        left.second->right = root;
        root->left = left.second;
    }

    if (right.first != root) {
        root->right = right.first;
        right.first->left = root;
    }
 
    return {left.first, right.second};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void  dfs(Node* root) {
       if (!root) return;
       
       //访问左边
       dfs(root->left);

       //中序遍历
       if (!pre) {
           head = root;
       }
       else {
           pre->right = root;
           root->left = pre;
       }
       pre = root;

       //访问右边
       dfs(root->right);
   }

Posted on Edited on In , Valine:

判断该数组是不是某二叉搜索树的后序遍历的结果-题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

样例
输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

判断该数组是不是某二叉搜索树的后序遍历的结果-总体思路

分为几步：
（1）根据后序遍历序列的定义，最右边的元素是中间节点X，并且左子树的元素均小于X，右子树的元素均大于X
（2）顺序扫描，找到左右子树的分割点Y(分割点左边都小于X)
（3）从分割点Y继续扫描，确认是否有bad case，有的话，直接返回不合法
（4）递归处理左右两部分

判断该数组是不是某二叉搜索树的后序遍历的结果-代码实现

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
class Solution {
public:
    vector<int> s;
    bool dfs(int l, int r) {
        if (l >= r) return true;
        
        //找到分界点
        int k = l;
        while (k < r && s[k] < s[r]) k++;
        
        //确认分界点之后的元素是否都足够大
        for (int i = k; i< r; ++i) {
            if (s[i] < s[r]) {
                return false;
            }
        }
        
        //递归处理
        return dfs(l, k - 1) && dfs(k, r - 1);
        
    }
    
    bool verifySequenceOfBST(vector<int> sequence) {
        s = sequence;
        if (s.empty()) return true;
        return dfs(0, s.size() - 1);
    }
};