h****p 发帖数: 87 | 1 Find the node with given value in binary tree in in-order way,and return it;
PS: the binary tree may include two nodes with the same value.
感觉老写不对
哪位大牛分享下solution?
谢谢 |
b**********5 发帖数: 7881 | 2 什么叫 in in-order way, 是不是就写个inorder walk, 然后顺便查查是不是equal? |
T******e 发帖数: 157 | 3 本菜鸟的想法:
inorder遍历的时候如果目标是当前节点,检查左子树(如果有返回值返回)
如果目标不是当前节点,返回左子树(假如有值的话),否则返回右子树 |
i********s 发帖数: 22 | 4 不知道理解得是否正确,
如果存在多个值等于val,则返回in-order遍历最先找到的这个节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
bool find(TreeNode* root, TreeNode*& ret, int val) {
if (root == NULL) {
return false;
}
if (root->left != NULL && find(root->left, ret, val)) {
return true;
}
if (root->val == val) {
ret = root;
return true;
}
if (root->right != NULL && find(root->right, ret, val)) {
return true;
}
return false;
} |
s********u 发帖数: 1109 | 5 首先要确定下是不是BST,这里假定不是。
TreeNode *search(TreeNode *root, int key ){
if( root == NULL )
return NULL;
TreeNode *res = search(root->left,key);
if(res)
return res;
if(root->val == key )
return root;
res = search(root->right,key);
return res;
}
|
s********u 发帖数: 1109 | 6 既然root已经处理了null的情况,个人觉得就不用去判断root->left或root->right是
否为NULL了。或者反之。
【在 i********s 的大作中提到】 : 不知道理解得是否正确, : 如果存在多个值等于val,则返回in-order遍历最先找到的这个节点 : struct TreeNode { : int val; : TreeNode* left; : TreeNode* right; : }; : bool find(TreeNode* root, TreeNode*& ret, int val) { : if (root == NULL) { : return false;
|