文章目录

• 题目描述
• 1. 后继结点
• 2. 前驱结点
• 测试结果及代码

题目描述

找出带父指针的二叉树中某结点的前驱、后继结点。

这里的前驱结点、后继结点指的是中序遍历的情况下，某结点的前一个、后一个结点

如果避免去中序遍历整棵树，则复杂度即当前结点距离它后继结点的距离

1. 后继结点

这里要考虑输入结点x是否有右子树的情况：

• 该结点x如果有右子树，它的后继结点一定是它右子树上最左的结点

由于中序遍历是 左中右 的，
如果一个结点有右子树，x打印了，则下一个打印的就是它右子树上的结点，
再下一个打印的就是它右子树上左边的结点

• 该结点x如果没有右子树，它的后继结点应当找到一个结点，它的左子树是以x结尾的，往上找直到某一个结点是它的父结点的左孩子，那个父就是原始结点x的后继结点

2. 前驱结点

有了后继结点的基础，前驱结点就很容易的，同样道理，考虑当前结点x是否有左子树：

• 如果当前结点x有左子树，就去找左子树中最右的那个结点，就是当前结点x的前驱
• 如果当前结点x没有左子树，就往上找，直到某一个结点是它的父结点的右孩子，那个父就是原始结点x的前驱结点

测试结果及代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
using namespace std;


struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	struct TreeNode *parent;
	TreeNode(int x) : val(x), left(NULL), right(NULL), parent(NULL) { }
};

class Solution {
public:
	
	TreeNode* getSuccessorNode(TreeNode *node) {
		if (node == NULL)
			return node;

		if (node->right != NULL) {
			return getLeftMost(node->right);
		}
		else {		
			TreeNode *p = node->parent;
			// 这里的p != NULL是整个树最右的一个结点，代表没有后继
			while (p != NULL && p->left != node) {
				node = p;
				p = node->parent;
			}
			return p;
		}
	}

	TreeNode* getLeftMost(TreeNode *node) {
		if (node == NULL)
			return node;
		while (node->left != NULL) {
			node = node->left;
		}
		return node;
	}

	TreeNode* getPrecursorNode(TreeNode *node) {
		if (node == NULL)
			return NULL;
		if (node->left != NULL) {
			return getRightMost(node->left);
		}
		else {
			TreeNode *p = node->parent;
			while (p != NULL && p->right != node) {
				node = p;
				p = node->parent;
			}
			return p;
		}
	}

	TreeNode* getRightMost(TreeNode *node) {
		if (node == NULL)
			return node;
		while (node->right != NULL) {
			node = node->right;
		}
		return node;
	}

	void in(TreeNode *head) {
		if (head != NULL) {
			stack<TreeNode*> stk;
			while (!stk.empty() || head != NULL) {
				if (head != NULL) {
					stk.push(head);
					head = head->left;	// 当前结点会把自己的左边全部压栈
				}
				else {
					head = stk.top();
					cout << head->val << " ";
					stk.pop();
					head = head->right;
				}
			}
		}
	}

};

int main(int argc, char* argv[]){

	TreeNode *head = new TreeNode(6);
	head->parent = NULL;
	head->left = new TreeNode(3);
	head->left->parent = head;
	head->left->left = new TreeNode(1);
	head->left->left->parent = head->left;
	head->left->left->right = new TreeNode(2);
	head->left->left->right->parent = head->left->left;
	head->left->right = new TreeNode(4);
	head->left->right->parent = head->left;
	head->left->right->right = new TreeNode(5);
	head->left->right->right->parent = head->left->right;
	head->right = new TreeNode(9);
	head->right->parent = head;
	head->right->left = new TreeNode(8);
	head->right->left->parent = head->right;
	head->right->left->left = new TreeNode(7);
	head->right->left->left->parent = head->right->left;
	head->right->right = new TreeNode(10);
	head->right->right->parent = head->right;

	Solution s;
	cout << "中序遍历：";
	s.in(head);
	cout << endl;
	TreeNode *test = head->left->left;
	string res = to_string(test->val) + " next: " + to_string(s.getSuccessorNode(test)->val);
	cout << res << endl;
	if (s.getPrecursorNode(test) == NULL) {
		res = to_string(test->val) + " pre: null";
		cout << res << endl;
	}

	test = head->left->left->right;
	res = to_string(test->val) + " next: " + to_string(s.getSuccessorNode(test)->val);
	cout << res << endl;
	res = to_string(test->val) + " pre: " + to_string(s.getPrecursorNode(test)->val);
	cout << res << endl;
	test = head->left;
	res = to_string(test->val) + " next: " + to_string(s.getSuccessorNode(test)->val);
	cout << res << endl;
	res = to_string(test->val) + " pre: " + to_string(s.getPrecursorNode(test)->val);
	cout << res << endl;
	test = head->left->right;
	res = to_string(test->val) + " next: " + to_string(s.getSuccessorNode(test)->val);
	cout << res << endl;
	res = to_string(test->val) + " pre: " + to_string(s.getPrecursorNode(test)->val);
	cout << res << endl;
	test = head->left->right->right;
	res = to_string(test->val) + " next: " + to_string(s.getSuccessorNode(test)->val);
	cout << res << endl;
	res = to_string(test->val) + " pre: " + to_string(s.getPrecursorNode(test)->val);
	cout << res << endl;
	test = head;
	res = to_string(test->val) + " next: " + to_string(s.getSuccessorNode(test)->val);
	cout << res << endl;
	res = to_string(test->val) + " pre: " + to_string(s.getPrecursorNode(test)->val);
	cout << res << endl;
	test = head->right->left->left;
	res = to_string(test->val) + " next: " + to_string(s.getSuccessorNode(test)->val);
	cout << res << endl;
	res = to_string(test->val) + " pre: " + to_string(s.getPrecursorNode(test)->val);
	cout << res << endl;
	test = head->right->left;
	res = to_string(test->val) + " next: " + to_string(s.getSuccessorNode(test)->val);
	cout << res << endl;
	res = to_string(test->val) + " pre: " + to_string(s.getPrecursorNode(test)->val);
	cout << res << endl;
	test = head->right;
	res = to_string(test->val) + " next: " + to_string(s.getSuccessorNode(test)->val);
	cout << res << endl;
	res = to_string(test->val) + " pre: " + to_string(s.getPrecursorNode(test)->val);
	cout << res << endl;
	test = head->right->right; // 10's next is null
	if (s.getSuccessorNode(test) == NULL) {
		res = to_string(test->val) + " next: null";
		cout << res << endl;
	}

	res = to_string(test->val) + " pre: " + to_string(s.getPrecursorNode(test)->val);
	cout << res << endl;
	return 0;
}```