题干:
代码(递归实现):
TreeNode* searchBST(TreeNode* root, int val){if(root == NULL || root-> val == val)return root;TreeNode* res;if(val > root->val) res = searchBST(root->right, val);if(val < root->val) res = searchBST(root->left, val);return res;
}
迭代实现:
TreeNode* searchBST(TreeNode* root, int val){if(root == NULL || root-> val == val)return root;while(root != NULL){if(val < root->val) root = root -> left;else if(val > root->val) root = root -> right;else return root;}return NULL;
}
谢天谢地,因为BST已经规划好了搜索顺序所以迭代法就不需要借用栈或是队列来遍历了。