[数据结构与算法]阿里面试的一道笔试题

之前阿里的一道现场笔试题目，求解二叉搜索树任意一个节点的后继节点（中序遍历）
现在贴在这里，更多考验的是心态

#include <iostream>
#include<vector>
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode* parent;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:

	TreeNode* getNextNode(TreeNode* curnode)
	{
		if (curnode->right)
		{
			curnode = curnode->right;
			while (curnode->left)
				curnode = curnode->left;
			return curnode;
		}
		else//没有右子树
		{

			TreeNode* p = curnode->parent;
			while (p != NULL &&p->val < curnode->val )
			{
				p = p->parent;
			}
			return p;

		}

	}
};

int main()
{
	Solution s;
	TreeNode* node1 = new TreeNode(20);
	TreeNode* node2 = new TreeNode(10);
	TreeNode* node3 = new TreeNode(30);
	TreeNode* node4 = new TreeNode(5);
	TreeNode* node5 = new TreeNode(25);
	TreeNode* node6 = new TreeNode(36);
	TreeNode* node7 = new TreeNode(7);
	TreeNode* node8 = new TreeNode(33);
	
	node1->left = node2;
	node1->right = node3;
	node1->parent = NULL;


	node2->left = node4;
	node2->right = NULL;
	node2->parent = node1;

	node3->left = node5;
	node3->right=node6;
	node3->parent = node1;

	node4->left = NULL;
	node4->right = node7;
	node4->parent = node2;

	node5->left = node5->right = NULL;
	node5->parent = node3;

	node6->left = node8;
	node6->right = NULL;
	node6->parent = node3;

	node7->left = node7->right = NULL;
	node7->parent = node4;

	node8->left = node8->right = NULL;
	node8->parent = node6;
	
	vector<TreeNode*> nextnodes;
	cout<<s.getNextNode(node1)->val<<endl;
	cout << s.getNextNode(node2)->val<<endl;;
	cout << s.getNextNode(node3)->val<<endl;;
	cout << s.getNextNode(node4)->val<<endl;;
	cout << s.getNextNode(node5)->val<<endl;;
	if (s.getNextNode(node6) == NULL)
		cout << "1111111111111111"<<endl;
	cout << s.getNextNode(node7)->val<<endl;;
	cout << s.getNextNode(node8)->val<<endl;;
	return 0;
}