Search in a Binary Search Tree
当根节点为空时返回NULL，否者判断根节点的val是否是搜索值，若是返回根节点。否者递归搜索左子树和右子树。
graph LR
F(start)-->a{根节点是否为空}
a--是-->b(返回NULL)
a--否-->c{根节点是否等于搜索值}
c--是-->e(返回根节点)
c--否-->g{根节点的值是否大于搜索值}
g--是-->h[递归遍历左子树]
g--否-->i[递归遍历右子树]
h-.->a
i-.->a
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
TreeNode* result;
if(!root)
return NULL;
if(root->val == val)
return result = root;
if(root->val > val)
result = searchBST(root->left, val);
else
result = searchBST(root->right, val);
return result;
}
};
Insert into a Binary Search Tree
如果是空树，直接将待插入数字插入根节点。否者根据根节点的值递归处理左子树或右子树。
graph LR
z[start]-->a{根结点是否为空}
a--是-->b[把数字插入根节点]
b-->nd[end]
a--否-->c[根结点的值是否大于待插入数字]
c--是-->d[递归处理左子树]
c--否-->e[递归处理右子树]
d-.->a
e-.->a
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root)
root = new TreeNode(val);
else if(root->val > val)
root->left = insertIntoBST(root->left, val);
else if(root->val < val)
root->right = insertIntoBST(root->right, val);
return root;
}
};