---

1.給一個數組構建二叉樹

思路：就是借助一個隊列實現層序遍歷的思想。
先將root節點入隊列，構造左右節點后，root取出來時，將其左右孩子都入隊列。

struct TreeNode
{unique_ptr<TreeNode> left;unique_ptr<TreeNode> right;int _val;TreeNode(int val):_val(val),left(nullptr),right(nullptr){}~TreeNode(){}
};//層序遍歷構建二叉樹
// 1 2 3 4 5
unique_ptr<TreeNode> BuildBinaryTreeFromLevelOrder(vector<int>& nums)
{if (nums.size() == 0){cout << "nums is empty!" << endl;}unique_ptr<TreeNode> root = make_unique<TreeNode>(nums[0]);queue<TreeNode*> q;q.push(root.get());int i = 1;while (!q.empty() && i < nums.size()){TreeNode* cur = q.front();q.pop();//先處理左子樹cur->left = make_unique<TreeNode>(nums[i]);q.push(cur->left.get());i++;//再處理右子樹if (i < nums.size()){cur->right = make_unique<TreeNode>(nums[i]);q.push(cur->right.get());}i++;}return root;
}

2.從前序遍歷和中序遍歷構建二叉樹

從前序遍歷和中序遍歷構建二叉樹

思路：

• 1.根據前序遍歷的根，先找到中序遍歷的根節點所在下標。
• 2.然后劃分成兩個區間進行遞歸即可。

注意事項：
previ是前序中的根節點下表，用來構建當前節點的。
所以構建完根節點后， 需要++previ，到達左子樹的根節點。
并且要傳引用。否則回到當前遞歸棧這一層時，會從原位置開始向下走

class Solution {
public:TreeNode* _buildTree(vector<int>& preorder,vector<int>& inorder,int& previ,int inbegin,int inend){if(inbegin > inend)return nullptr; //子區間遞歸結束了TreeNode* root = new TreeNode(preorder[previ]);//1.先在中序區間找根節點下標int rooti = 0;while(rooti <= inend){if(preorder[previ] == inorder[rooti])break;++rooti;}//2.分成左右子區間分別構建子樹。++previ; //根節點的下一個節點就是左子樹的根了root->left = _buildTree(preorder,inorder,previ,inbegin,rooti-1);//這里不要再++prei，因為遞歸構建左子樹時，會自己++prei,構建左子樹的最后//一個節點時，會先++prei，就到右子樹了。root->right = _buildTree(preorder,inorder,previ,rooti+1,inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {//根據前序遍歷的根，先找到中序遍歷的根節點所在下標。//然后劃分成兩個區間進行遞歸即可。int previ = 0; //傳參時一定是傳引用，否則回到當前遞歸棧這一層時//會從原位置開始向下走int inbegin = 0,inend = inorder.size()-1;return _buildTree(preorder,inorder,previ,inbegin,inend);}
};

3.二叉樹中的最大路徑和

二叉樹中的最大路徑和

思路：二叉樹中一條路的最大路徑和一定是該節點的左子樹的最大有效值與右子樹的最大有效值的最大值的和，再加上當前節點的值。
所以：

• 1.先求出左右子樹的最大有效值，再加上當前節點的值。
• 2.求有效值的過程，不斷更新最大路徑和。

這里注意兩個概念：

• 1.最大貢獻值是因為左子樹可能有幾十條路徑，需要選出最優的路徑，才是最大的貢獻。
  左右子樹的最大貢獻值加起來，再加上我當前節點的值之后，才組成最大路徑和（左右都是最優的路徑)。我的左子樹和右子樹兩條路徑選出來，比較后，選最大的，再加上我當前節點的值，然后向上交付，就能組成一條最優的路徑。
• 2.最大路徑和就是：左右子樹的最大貢獻值，加上我當前節點的值，就組成了一條完整的路徑。

別看這道題是困難題，如果想明白了后序遍歷，就一點不難。

class Solution {int max_val = INT_MIN; //保存最大的路徑和
public:int _paxPathSum(TreeNode* root){if(root == nullptr)return 0; //空節點的有效值為0//保存左右子樹的最大貢獻值int left_con = max(_paxPathSum(root->left),0);int right_con = max(_paxPathSum(root->right),0);//更新最大路徑和max_val = max(max_val,left_con + right_con + root->val);//返回貢獻值return root->val + max(left_con,right_con);}int maxPathSum(TreeNode* root) {_paxPathSum(root);return max_val;}
};