面试的时候求最小值我用了初始最大整数,居然...

stellari 发表于 2016-10-24 02:36
把minVal初始化成INT_MAX不是不可以，但是关键是你要清楚这可能会造成什么影响。如果仅是单纯地求容器内 ...

多谢解答,也不是单纯求了,就是比如validate bst的初始值之类的.

好像第一个node的INT_MAX和本身的INT_MAX会造成False,但是如果只有一个Node应该是True.

所以就应该完全避免使用INT_MAX了..?

finerve 发表于 2016-10-23 16:25
多谢解答,也不是单纯求了,就是比如validate bst的初始值之类的.

好像第一个node的INT_MAX和本身的INT_ ...

这类问题的处理方式大概有两种：
1.1. 把input为极值的情况单独处理。比如在代码里专门写如果输入时极大/小值该如何如何。
1.2. 如你所说，先判断下input为空在某些时候也可以。

2. 另外一个比较cheese的做法就是把input从int转成long，然后用LONG_MAX作为极大值去比。这样的好处是如果面试官认为可以的话实现起来最简单，坏处是面试官也可以顺着问：
“那如果input本身就是long怎么办？”
“那就用long long"
“那如果input本身就是long long怎么办”
“...DOUBLE_MAX?????”

所以看情况。其实根据以前的经验不少情况下方法2就可以了

finerve 发表于 2016-10-23 16:25
多谢解答,也不是单纯求了,就是比如validate bst的初始值之类的.

好像第一个node的INT_MAX和本身的INT_ ...

恩就validate bst这道题来说的话：

比如我想用inorder traversal, 比上一个遍历过的值和现在node的值，那么有多个做法：

1. 把“上一个遍历过的值”设成LONG_MIN. 这样的做法代码如下：

1. bool helper(TreeNode *root, long &prev_val) {
   
2.     if (root == NULL) return true;
   
3.     bool left_valid = helper(root->left, prev_val);
   
4.     if (!left_valid) return false;
   
5.     if (prev_val >= root->val) return false;
   
6.     prev_val = root->val;
   
7.     return helper(root->right, prev_val);
   
8. }
   
9.    
   
10. bool isValidBST(TreeNode* root) {
    
11.     long prev_val = LONG_MIN;
    
12.     return helper(root, prev_val);

复制代码

2. 当然“上一个遍历过的值”是可以初始化成INT_MIN的，但是你需要代码里专门处理下如果这个数里面存在INT_MIN怎么办（比如最左节点是INT_MIN)。一个可行的处理方法就是看你是不是已经遍历过了最左节点，因为一个正确的BST里，INT_MIN只可能存在于最左节点。这样的代码如下：

1. bool helper(TreeNode *root, int &prev_num, bool &visited_leftmost) {
   
2.     if (root == NULL) return true;
   
3.     bool left_valid = helper(root->left, prev_num, visited_leftmost);
   
4.     if (!left_valid) return false;
   
5.         
   
6.     if (root->val == INT_MIN) {
   
7.         if (visited_leftmost) return false;
   
8.         else visited_leftmost = true;
   
9.     } else if (root->val <= prev_num) return false;
   
10.     visited_leftmost = true;
    
11.     prev_num = root->val;
    
12.     return helper(root->right, prev_num, visited_leftmost);
    
13. }
    
14.    
    
15. bool isValidBST(TreeNode* root) {
    
16.     int prev_num = INT_MIN;
    
17.     bool visited_leftmost = false;
    
18.     return helper(root, prev_num, visited_leftmost);
    
19. }

复制代码

当然你也可以采取另外一种方式validate bst，那就是看当前节点的值是不是比左子树的最大值大且比右子树的最小值小。这类做法也有写法可以把你的最大值最小值用INT_MIN和INT_MAX初始化而不用担心树里有INT_MIN和INT_MAX的node。提示一下：用postorder traversal做。

用Integer类型，设置为null就好了，判断的时候多加一个if

yxyxyx 发表于 2016-10-24 05:31
恩就validate bst这道题来说的话：

比如我想用inorder traversal, 比上一个遍历过的值和现在node的值 ...

大神,如果想用迭代+in-order的方法判断valid bst,"上一个node"变量不能设初始值为root,如果也不能设初始值为最小int,只能初始为null 再加判断了是吗?

xietao0221 发表于 2016-10-24 05:57
用Integer类型，设置为null就好了，判断的时候多加一个if

这方法好,虽然很朴素,不过感觉各种情况通吃啊~

finerve 发表于 2016-10-24 07:21
这方法好,虽然很朴素,不过感觉各种情况通吃啊~

你这个不是技术问题...

阿三一旦发问，不要怂，直接干. 不服就举例，摁不死他就是被摁死. 千万不要被阿三带着走.....人家未必就是想黑你，但是阿三就这风格，就是喜欢突然岔开去...搞着搞着最后面的人崩了.

finerve 发表于 2016-10-23 19:19
大神,如果想用迭代+in-order的方法判断valid bst,"上一个node"变量不能设初始值为root,如果也不能设初始 ...

恩听起来你用的是Java？如果java里有NULL定义的话那自然最好了，c++里的int不幸不能设定成NULL，所以没有这个选项

yxyxyx 发表于 2016-10-24 09:24
恩听起来你用的是Java？如果java里有NULL定义的话那自然最好了，c++里的int不幸不能设定成NULL，所以没有 ...

其实如果没有null也没关系，可以另外设置一个bool变量作为是否第一个值已经赋值，其实是一个道理，只是代码会多一些东西。

finerve 发表于 2016-10-23 15:19
预先判断input为空能不能排除掉你说的corner case? 求指正

我忘了我的case了。应该是可以，总之就是要对corner case做特殊处理，input为空当然是corner case的一种。