題型

226.翻轉二叉樹

思路：把每一個節點的左右孩子交換一下

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;swap(root->left, root->right);  // 中invertTree(root->left);         // 左invertTree(root->right);        // 右return root;}
};

101. 對稱二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的。

思路：使用隊列來比較兩個樹（根節點的左右子樹）是否相互翻轉

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == NULL) return true;queue<TreeNode*> que;que.push(root->left);   // 將左子樹頭結點加入隊列que.push(root->right);  // 將右子樹頭結點加入隊列while (!que.empty()) {  // 接下來就要判斷這兩個樹是否相互翻轉TreeNode* leftNode = que.front(); que.pop();TreeNode* rightNode = que.front(); que.pop();if (!leftNode && !rightNode) {  // 左節點為空、右節點為空，此時說明是對稱的continue;}// 左右一個節點不為空，或者都不為空但數值不相同，返回falseif ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {return false;}que.push(leftNode->left);   // 加入左節點左孩子que.push(rightNode->right); // 加入右節點右孩子que.push(leftNode->right);  // 加入左節點右孩子que.push(rightNode->left);  // 加入右節點左孩子}return true;}
};

222.完全二叉樹的節點個數

給出一個完全二叉樹，求出該樹的節點個數。

在這里插入代碼片

示例 1：

輸入：root = [1,2,3,4,5,6]
輸出：6
示例 2：

輸入：root = []
輸出：0
示例 3：

輸入：root = [1]
輸出：1

思路：本題直接就是求有多少個節點，無腦存進結果變量就行了。

class Solution {
public:int countNodes(TreeNode* root) {if (root == nullptr) return 0;TreeNode* left = root->left;TreeNode* right = root->right;int leftDepth = 0, rightDepth = 0; // 這里初始為0是有目的的，為了下面求指數方便while (left) {  // 求左子樹深度left = left->left;leftDepth++;}while (right) { // 求右子樹深度right = right->right;rightDepth++;}if (leftDepth == rightDepth) {return (2 << leftDepth) - 1; // 注意(2<<1) 相當于2^2，所以leftDepth初始為0}return countNodes(root->left) + countNodes(root->right) + 1;}
};

110.平衡二叉樹

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。

思路：比較高度，必然是要后序遍歷。

遞歸三步曲分析：
1.明確遞歸函數的參數和返回值
參數：當前傳入節點。 返回值：以當前傳入節點為根節點的樹的高度。
2.明確終止條件
遞歸的過程中依然是遇到空節點了為終止，返回0，表示當前節點為根節點的樹高度為0
3.明確單層遞歸的邏輯
如何判斷以當前傳入節點為根節點的二叉樹是否是平衡二叉樹呢？當然是其左子樹高度和其右子樹高度的差值。

分別求出其左右子樹的高度，然后如果差值小于等于1，則返回當前二叉樹的高度，否則返回-1，表示已經不是二叉平衡樹了。

class Solution {
public:// 返回以該節點為根節點的二叉樹的高度，如果不是平衡二叉樹了則返回-1int getHeight(TreeNode* node) {if (node == NULL) {return 0;}int leftHeight = getHeight(node->left);if (leftHeight == -1) return -1;int rightHeight = getHeight(node->right);if (rightHeight == -1) return -1;return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);}bool isBalanced(TreeNode* root) {return getHeight(root) == -1 ? false : true;}
};int getHeight(TreeNode* node) {if (node == NULL) {return 0;}int leftHeight = getHeight(node->left);if (leftHeight == -1) return -1;int rightHeight = getHeight(node->right);if (rightHeight == -1) return -1;return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}

257. 二叉樹的所有路徑

給定一個二叉樹，返回所有從根節點到葉子節點的路徑。

說明: 葉子節點是指沒有子節點的節點。

思路：把路徑記錄下來，需要回溯來回退一個路徑再進入另一個路徑。

遞歸三部曲

1.遞歸函數參數以及返回值

傳入根節點，記錄每一條路徑的path，和存放結果集的result

2.確定遞歸終止條件

當 cur不為空，其左右孩子都為空的時候，就找到葉子節點。

3.確定單層遞歸邏輯

回溯要和遞歸永遠在一起

class Solution {
private:void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {path.push_back(cur->val); // 中，中為什么寫在這里，因為最后一個節點也要加入到path中 // 這才到了葉子節點if (cur->left == NULL && cur->right == NULL) {string sPath;for (int i = 0; i < path.size() - 1; i++) {sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]);result.push_back(sPath);return;}if (cur->left) { // 左 traversal(cur->left, path, result);path.pop_back(); // 回溯}if (cur->right) { // 右traversal(cur->right, path, result);path.pop_back(); // 回溯}}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if (root == NULL) return result;traversal(root, path, result);return result;}
};

404.左葉子之和

計算給定二叉樹的所有左葉子之和。

思路：如果該節點的左節點不為空，該節點的左節點的左節點為空，該節點的左節點的右節點為空，則找到了一個左葉子

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right== NULL) return 0;int leftValue = sumOfLeftLeaves(root->left);    // 左if (root->left && !root->left->left && !root->left->right) { // 左子樹就是一個左葉子的情況leftValue = root->left->val;}int rightValue = sumOfLeftLeaves(root->right);  // 右int sum = leftValue + rightValue;               // 中return sum;}
};

513.找樹左下角的值

給定一個二叉樹，在樹的最后一行找到最左邊的值。

思路：

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result = 0;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (i == 0) result = node->val; // 記錄最后一行第一個元素if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

112. 路徑總和

給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目標和。

說明: 葉子節點是指沒有子節點的節點。

思路：

參數：需要二叉樹的根節點，還需要一個計數器，這個計數器用來計算二叉樹的一條邊之和是否正好是目標和，計數器為int型。
讓計數器count初始為目標和，然后每次減去遍歷路徑節點上的數值。
如果最后count == 0，同時到了葉子節點的話，說明找到了目標和。
回溯隱藏在traversal(cur->left, count - cur->left->val)這里， 因為把count - cur->left->val 直接作為參數傳進去，函數結束，count的數值沒有改變。

class Solution {
private:bool traversal(TreeNode* cur, int count) {if (!cur->left && !cur->right && count == 0) return true; // 遇到葉子節點，并且計數為0if (!cur->left && !cur->right) return false; // 遇到葉子節點直接返回if (cur->left) { // 左count -= cur->left->val; // 遞歸，處理節點;if (traversal(cur->left, count)) return true;count += cur->left->val; // 回溯，撤銷處理結果}if (cur->right) { // 右count -= cur->right->val; // 遞歸，處理節點;if (traversal(cur->right, count)) return true;count += cur->right->val; // 回溯，撤銷處理結果}return false;}public:bool hasPathSum(TreeNode* root, int sum) {if (root == NULL) return false;return traversal(root, sum - root->val);}
};

106.從中序與后序遍歷序列構造二叉樹

根據一棵樹的中序遍歷與后序遍歷構造二叉樹。

注意: 你可以假設樹中沒有重復的元素。

思路：

第一步：如果數組大小為零的話，說明是空節點了。

第二步：如果不為空，那么取后序數組最后一個元素作為節點元素。

第三步：找到后序數組最后一個元素在中序數組的位置，作為切割點

第四步：切割中序數組，切成中序左數組和中序右數組 （順序別搞反了，一定是先切中序數組）

第五步：切割后序數組，切成后序左數組和后序右數組

第六步：遞歸處理左區間和右區間

class Solution {
private:// 中序區間：[inorderBegin, inorderEnd)，后序區間[postorderBegin, postorderEnd)TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {if (postorderBegin == postorderEnd) return NULL;int rootValue = postorder[postorderEnd - 1];TreeNode* root = new TreeNode(rootValue);if (postorderEnd - postorderBegin == 1) return root;int delimiterIndex;for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 切割中序數組// 左中序區間，左閉右開[leftInorderBegin, leftInorderEnd)int leftInorderBegin = inorderBegin;int leftInorderEnd = delimiterIndex;// 右中序區間，左閉右開[rightInorderBegin, rightInorderEnd)int rightInorderBegin = delimiterIndex + 1;int rightInorderEnd = inorderEnd;// 切割后序數組// 左后序區間，左閉右開[leftPostorderBegin, leftPostorderEnd)int leftPostorderBegin =  postorderBegin;int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 終止位置是 需要加上 中序區間的大小size// 右后序區間，左閉右開[rightPostorderBegin, rightPostorderEnd)int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);int rightPostorderEnd = postorderEnd - 1; // 排除最后一個元素，已經作為節點了root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;// 左閉右開的原則return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());}
};

654.最大二叉樹

給定一個不含重復元素的整數數組。一個以此數組構建的最大二叉樹定義如下：

二叉樹的根是數組中的最大元素。
左子樹是通過數組中最大值左邊部分構造出的最大二叉樹。
右子樹是通過數組中最大值右邊部分構造出的最大二叉樹。
通過給定的數組構建最大二叉樹，并且輸出這個樹的根節點。

思路：構造樹一般采用的是前序遍歷，因為先構造中間節點，然后遞歸構造左子樹和右子樹。

class Solution {
private:// 在左閉右開區間[left, right)，構造二叉樹TreeNode* traversal(vector<int>& nums, int left, int right) {if (left >= right) return nullptr;// 分割點下標：maxValueIndexint maxValueIndex = left;for (int i = left + 1; i < right; ++i) {if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;}TreeNode* root = new TreeNode(nums[maxValueIndex]);// 左閉右開：[left, maxValueIndex)root->left = traversal(nums, left, maxValueIndex);// 左閉右開：[maxValueIndex + 1, right)root->right = traversal(nums, maxValueIndex + 1, right);return root;}
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return traversal(nums, 0, nums.size());}
};