题解 | #二叉树中的最大路径和#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxPathSum(TreeNode* root) {
      if (root == nullptr) {
        return 0;
      }
      
      int res = -0xff;
      std::queue<TreeNode *> q;
      std::vector<TreeNode *> list;
      
      q.push(root);
      
      while (!q.empty()) {
        int size = q.size();
        
        for (int i = 0; i < size; ++i) {
          TreeNode *tmp = q.front();
          q.pop();
          
          list.push_back(tmp);
          
          if (tmp->left) {
            q.push(tmp->left);
          }
          if (tmp->right) {
            q.push(tmp->right);
          }
        }
      }
      
      //  从叶子结点向上递推
      for (int i = list.size() - 1; i >= 0; --i) {
        TreeNode *tmp = list[i];
        
        //  叶子结点
        if (tmp->left == nullptr && tmp->right == nullptr) {
          res = std::max(res, tmp->val);
        } else {
          int left = 0, right = 0;
          if (tmp->left) {
            left = tmp->left->val;
          }
          if (tmp->right) {
            right = tmp->right->val;
          }
          int old_tmp = tmp->val;
          //  当前结点只能取根，根左，根右三者中最大值，如果取左根右，那么从父结点访问下来会有结点被重复访问
          tmp->val = std::max(std::max(left, right) + tmp->val, tmp->val);
          //  最终结果可以单取一棵树
          //  根结点，根左，根右，左根右四者中取最大值
          res = std::max(res, std::max(old_tmp + left + right, tmp->val));
        }
      }
      
      return res;
    }
};