Find the node with given value in binary tree in in-order - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Find the node with given value in binary tree in in-order

Find the node with given value in binary tree in in-order# JobHunting - 待字闺中

h*p2013-10-11 07:10

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*52013-10-11 07:10

2 楼

什么叫 in in-order way，是不是就写个inorder walk，然后顺便查查是不是equal?

T*e2013-10-11 07:10

3 楼

本菜鸟的想法：
inorder遍历的时候如果目标是当前节点，检查左子树（如果有返回值返回）
如果目标不是当前节点，返回左子树（假如有值的话），否则返回右子树

i*s2013-10-11 07:10

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*u2013-10-11 07:10

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*u2013-10-11 07:10

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;