[Lintcode]Inorder Successor in Binary Search Tree(DFS)

题意

略

分析

1.首先要了解到BST的中序遍历是递增序列

2.我们用一个临时节点tmp储存p的中序遍历的下一个节点，如果p->right不存在，那么tmp就是从root到p的路径中大于p->val的最小数，否则就遍历p的右子树，找到最左边的节点即可

代码

class Solution {

public:

	/*

	 * @param root: The root of the BST.

	 * @param p: You need find the successor node of p.

	 * @return: Successor of p.

	 */

	TreeNode * tmp;

	TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {

		// write your code here'

		if (root == nullptr || p == nullptr) {

			return root;

		}

		tmp = nullptr;

		if (p->right == nullptr) {

			dfs(root, p);

			return tmp;

		}

		p = p->right;

		while (p->left != nullptr) {

			p = p->left;

		}

		return p;

	}

	void dfs(TreeNode * root, TreeNode * p) {

		if (root->val == p->val) {

			return ;

		}

		if (root->val > p->val) {

			tmp = root;

			dfs(root->left, p);

		}

		if (root->val < p->val) {

			dfs(root->right, p);

		}

	}

};

巴特西

[Lintcode]Inorder Successor in Binary Search Tree(DFS)

题意

分析

代码

最新文章

热门文章