LeetCode

LeetCode-BST 找前驱与后继结点

描述：
加入构造了一BST： 

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

现在要找到每个结点的前驱和后继结点。

思路：

可以将树的所有结点有序存储，后对于这个有序的数组操作。这里给出递归的思路。

  1. 对于前驱结点。

    第一步，首先搜索目标结点，即谁的前驱。这个过程是左->中->右中序遍历，过程中记录target结点属于第几大的结点，将结果保存到count中。

    第二步。重新左->中->右中序遍历，找到第count-1大的结点，即第一个比target小的结点。

  2. 对于后继结点。

    第一步，首先搜索目标结点，即谁的后驱。这个过程是左->中->右中序遍历，过程中记录target结点属于第几大的结点，将结果保存到count中。

    第二步。重新左->中->右中序遍历，找到第count+1大的结点，即第一个比target大的结点。

实现过程：

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
class Sol_successor_predecessor{
public:
/// 前驱结点的入口函数
	void predecessor(TreeNode* root, const TreeNode* const target, int count){
        // 遍历的count_
		inOrder(root, target, count);
        // 搜索第count_-1的结点
		predecessor_(root, target);
		if (res_)
			cout<<"predecessor node: "<<res_->val<<endl;
		else
			cout<<"predecessor node: nullptr"<<endl;
        // 重置
		count_=0;
		res_=nullptr;
		
	}
/// 后继结点的入口函数
	void successor(TreeNode* root, const TreeNode* const target, int count){
        // 遍历的count_
		inOrder(root, target, count);
        // 搜索第count_+1的结点
		successor_(root, target);
		if (res_)
			cout<<"successor node: "<<res_->val<<endl;
		else
			cout<<"successor node: nullptr"<<endl;
        // 重置
		count_=0;
		res_=nullptr;
	}


private:
	int count_ = 0;
	TreeNode* res_ = nullptr;

/// find the predecessor when count_ decreased to 1
	void predecessor_(TreeNode* root, const TreeNode* const target){
		if (root!=nullptr ){
            predecessor_(root->left, target);  
			count_--; 
            // 直到count_ 减掉count_-1个数后，找到前驱结点
			if (count_ == 1){
				res_ = root;
				return;
			}
            predecessor_(root->right, target);
        }
	}
/// find the successor when count_ decreased to -1
	void successor_(TreeNode* root, const TreeNode* const target){
		if (root!=nullptr ){
            successor_(root->left, target);  
			count_--; 
            // 直到count_ 减掉count_+1个数后，找到后继结点
			if ( count_ == -1){
				res_ = root;
				return;
			}
            successor_(root->right, target);
        }
	}

/// traverse to find the target node, and keep counting
	void inOrder(TreeNode* root, const TreeNode* const target, int& count){
        if (root!=NULL){
            inOrder(root->left, target, count);  
			count++;
			if (root->val == target->val){
                // 记录target结点是第几大的结点
				count_ = count;
				return;
			}  
            inOrder(root->right, target, count);
        }
    }
};

过程如注释。测试：

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
/// 后续遍历 用于销毁Tree
void destroyTree(TreeNode* root){
	if (root){
		destroyTree(root->left);
		destroyTree(root->right);
		delete root;
		root = nullptr;
		return;
	}
}

int main(int argc, char** argv){
	TreeNode* root = new TreeNode(4);
	TreeNode* node1 = new TreeNode(2);
	TreeNode* node2 = new TreeNode(6);
	TreeNode* node3 = new TreeNode(1);
	TreeNode* node4 = new TreeNode(3);
	TreeNode* node5 = new TreeNode(5);
	TreeNode* node6 = new TreeNode(7);

/// create a tree
	root->left = node1;
	root->right = node2;

	node1->left = node3;
	node1->right = node4;

	node2->left = node5;
	node2->right = node6;

/// create a vector
	vector<TreeNode*> treeVec = {node3,node1,node4,root,node5, 
								node2, node6};
	Sol_successor_predecessor sol;
	for (auto item: treeVec){
		sol.predecessor(root, item, 0);
		sol.successor(root, item, 0);
	}
/// 销毁
    destroyTree(root);
    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
target node: 1
predecessor node: nullptr
successor node: 2

target node: 2
predecessor node: 1
successor node: 3

target node: 3
predecessor node: 2
successor node: 4

target node: 4
predecessor node: 3
successor node: 5

target node: 5
predecessor node: 4
successor node: 6

target node: 6
predecessor node: 5
successor node: 7

target node: 7
predecessor node: 6
successor node: nullptr

结果正确。