【408DS算法题】028基础-查找二叉树的最大值结点

Index

• • 题目
  • 分析实现
  • 总结

题目

给定二叉树的根节点，找到二叉树中结点值最大的结点。

分析实现

对于查找二叉树中的最大值结点，在二叉树的遍历（DFS、层次遍历）的基础上进行修改可以轻松地达成这一目的。
本文中选用的是相对直观的后序遍历，具体实现如下：

BTNode* findMax(BTNode *root){
    if(root==NULL) 
        return NULL;
    BTNode *maxLeft = findMax(root->left);
    BTNode *maxRight = findMax(root->right);
    
    BTNode *maxNode = root;
    if(maxLeft && maxLeft->val>maxNode->val)
        maxNode = maxLeft;
    if(maxRight && maxRight->val>maxNode->val)
        maxNode = maxRight;
    return maxNode;
}

总结

以上就是使用后序遍历查找二叉树的最大值结点的实现。

需要额外注意的是，注意maxLeft和maxRight指向NULL的情况。本文的写法考虑到这种情况，书写也相对简洁，思路值得参考。