1. 二叉樹不易構建
在leetcode中刷題時，如果沒有會員就需要將代碼拷貝到本地的編譯器進行調試。但是leetcode中有一類題可謂是毒瘤，那就是二叉樹的題。
要調試二叉樹有關的題需要根據測試用例給出的前序遍歷，自己構建一個二叉樹，非常不方便。
作為一個懶人，在此之前我的解決辦法就是硬看程序，反復檢查，但是確實有點折磨了。
前幾天在刷二叉樹有關的題時心血來潮寫了一個函數來幫助構建二叉樹。
2. 代碼
#include <iostream>
#include <queue>
using namespace std;
#define null -1struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};TreeNode* construct(vector<int>& nums)
{int n = nums.size();TreeNode* newnode = nullptr;queue<TreeNode*> q;if (n != 0){int i = 0;newnode = new TreeNode(nums[i++]);q.push(newnode);while (!q.empty()){if (i < n && nums[i] != null){q.front()->left = new TreeNode(nums[i]);q.push(q.front()->left);}i++;if (i < n && nums[i] != null){q.front()->right = new TreeNode(nums[i]);q.push(q.front()->right);}i++;q.pop();}}return newnode;
}leetcode給出的前序遍歷中，空結點通常用null來表示，在程序中我們可以用一個數據范圍之外的數來表示空結點，并將null定義為這個數。上面的代碼中用的是-1。
我們用這個函數來幫助我們調試上面的這道題：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define null -1struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:TreeNode* ans;int count, ansCount;int dfs(TreeNode* root){if (root == nullptr) return 0;count++;int left = dfs(root->left);int right = dfs(root->right);count--;if (left == right && count + left >= ansCount){ans = root;ansCount = count + left;}return max(left, right) + 1;}TreeNode* lcaDeepestLeaves(TreeNode* root) {ans = nullptr;count = ansCount = 0;dfs(root);return ans;}
};TreeNode* construct(vector<int>& nums)
{int n = nums.size();TreeNode* newnode = nullptr;queue<TreeNode*> q;if (n != 0){int i = 0;newnode = new TreeNode(nums[i++]);q.push(newnode);while (!q.empty()){if (i < n && nums[i] != null){q.front()->left = new TreeNode(nums[i]);q.push(q.front()->left);}i++;if (i < n && nums[i] != null){q.front()->right = new TreeNode(nums[i]);q.push(q.front()->right);}i++;q.pop();}}return newnode;
}int main()
{vector<int> nums = { 3,5,1,6,2,0,8,null,null,7,4 };cout << Solution().lcaDeepestLeaves(construct(nums))->val << endl;
}這下就方便多了。
如果函數的返回值是 TreeNode* 的話，主函數的寫法也可以直接照搬。
)
