632 二叉树的最大节点

原题网址： http://www.lintcode.com/zh-cn/problem/binary-tree-maximum-node/#

在二叉树中寻找值最大的节点并返回。

您在真实的面试中是否遇到过这个题？

Yes

样例

给出如下一棵二叉树：

     1
   /   
 -5     2
 /    /  
0   3 -4  -5

返回值为 3 的节点。

标签

二叉树

方法：递归。

我是非常不擅长递归的，每次碰到递归都要想半天，递归返回值那里真的不好理解ORZ……而且一个递归式还好，二叉树这种两个递归式的真的碰到就懵逼……

首先在maxNode函数外定义了一个节点来保存最大节点，然后再定义一个int型整数，注意，该整数必须足够小，这里参考：C/C++语言中的int等基本数据类型所能表示的最大值最小值

为什么在函数外定义呢，因为如果定义在函数内，每次递归最大值与最大节点都会被重新赋值，即丢掉了上次对比时的值，这样就失去了比较的意义。

另外，题目没有给出二叉树节点的定义，按照经验猜测一番TreeNode应该是酱婶的：

class TreeNode
{
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int v)
{
val=v;
left=NULL;
right=NULL;
}
};

 1 class Solution {
 2 public:
 3     /**
 4      * @param root the root of binary tree
 5      * @return the max node
 6      */
 7      TreeNode *maxValNode;
 8     int maxVal;
 9     Solution()
10     {
11         maxValNode=NULL;
12         maxVal=1<<(sizeof(int)*8-1);
13     }
14      
15      
16     TreeNode* maxNode(TreeNode* root) {
17         // Write your code here
18         if (root!=NULL)
19         {
20             /TreeNode *maxVal=root->val;//若定义在函数内每次递归被重新赋值(无论赋何值)，算法失效;
21             int maxValNode=root;*/
22 
23             if (root->val>maxVal)
24             {
25                 maxVal=root->val;
26                 maxValNode=root;
27             }
28 
29             if (root->left!=NULL)
30             {
31                 maxValNode=maxNode(root->left);
32             }
33             if (root->right!=NULL)
34             {
35                 maxValNode=maxNode(root->right);
36             }
37 
38             return maxValNode;
39         }
40         else
41         {
42              return NULL;
43         }
44     }
45 };

方法二：

依旧是递归，但不用在函数外定义最大值及最大节点，参考：https://blog.csdn.net/yaomf/article/details/69789293

说一点自己的理解，这个方法递归的终止条件是找到叶子结点，然后将叶子结点返回，与其根节点对比值的大小，将较大的值赋值给根节点，继续返回该根节点向上比较。

上机测试了下，返回节点中的val的确是最大数值，但返回的节点地址不是最大节点地址，且部分二叉树节点中的数值被改变，函数执行完原二叉树变了。

但是在lintcode上可以通过，这个不影响。

 1 /**
 2  * Definition of TreeNode:
 3  * class TreeNode {
 4  * public:
 5  *     int val;
 6  *     TreeNode *left, *right;
 7  *     TreeNode(int val) {
 8  *         this->val = val;
 9  *         this->left = this->right = NULL;
10  *     }
11  * }
12  */
13 
14 class Solution {
15 public:
16     /*
17      * @param root: the root of tree
18      * @return: the max node
19      */
20     TreeNode * maxNode(TreeNode * root) {
21         // write your code here
22         if(root==NULL) return NULL;  
23         TreeNode *left=root;    
24         TreeNode *right=root;    
25         if (root->left!=NULL)   
26             left=maxNode(root->left);    
27         if (root->right!=NULL)   
28             right=maxNode(root->right);    
29         if (left->val>root->val)  
30             root->val=left->val;  
31         if (right->val>root->val)  
32             root->val=right->val;  
33         return root; 
34     }
35 };

其他参考：

https://www.cnblogs.com/zwxblog/p/7735095.html