[leetcode] 樹（Ⅰ）
- 2020 年 4 月 5 日
- 筆記
均為 Simple 難度的水題。
二叉樹的中序遍歷
題目[94]：給定一個二叉樹，返回它的中序 遍歷。
解題思路：Too simple.
class Solution { public: vector<int> inorderTraversal(TreeNode *root) { return inorderNonRec(root); vector<int> v; innerTraversal(root, v); return v; } void innerTraversal(TreeNode *p, vector<int> &v) { if (p == nullptr) return; innerTraversal(p->left, v); v.push_back(p->val); innerTraversal(p->right, v); } vector<int> inorderNonRec(TreeNode *root) { vector<int> v; if (root != nullptr) { stack<TreeNode *> s; auto p = root; while (!s.empty() || p != nullptr) { if (p != nullptr) { s.push(p); p = p->left; } else { p = s.top(), s.pop(); v.push_back(p->val); p = p->right; } } } return v; } }; 相同的樹
題目[100]：給定兩個二叉樹，編寫一個函數來檢驗它們是否相同。如果兩個樹在結構上相同，並且節點具有相同的值，則認為它們是相同的。
示例
輸入: 1 1 / / 2 3 2 3 [1,2,3], [1,2,3] 輸出: true 解題思路：遞歸。
#include "leetcode.h" class Solution { public: bool isSameTree(TreeNode *p, TreeNode *q) { return innerCheck(p, q); } bool innerCheck(TreeNode *p, TreeNode *q) { if ((p == nullptr) ^ (q == nullptr)) return false; if (p == nullptr && q == nullptr) return true; if (p->val != q->val) return false; return innerCheck(p->left, q->left) && innerCheck(p->right, q->right); } }; 對稱二叉樹
題目[101]：給定一個二叉樹，檢查它是否是鏡像對稱的。
示例
input: 1 / 2 2 / / 3 4 4 3 output: true 解題思路：遞歸。
class Solution { public: bool isSymmetric(TreeNode *root) { if (root == nullptr) return true; return innerCheck(root->left, root->right); } bool innerCheck(TreeNode *p, TreeNode *q) { if ((p == nullptr) ^ (q == nullptr)) return false; if (p == nullptr) return true; if (p->val != q->val) return false; return innerCheck(p->left, q->right) && innerCheck(p->right, q->left); } }; 二叉樹的最大深度
題目[104]：給定一個二叉樹，找出其最大深度。二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
示例
input: 3 / 9 20 / 15 7 output: 3 解題思路：DFS 。
#define max(a, b) ((a) > (b) ? (a) : (b)) class Solution { public: int maxDepth(TreeNode *root) { return dfs(root); } int dfs(TreeNode *p) { if (p == nullptr) return 0; int a = dfs(p->left), b = dfs(p->right); return max(a, b) + 1; } }; 值得注意的是，不能 return max(dfs(p->lect), dfs(p->right)) + 1，因為宏展開後就會執行 4 次 DFS 。
二叉樹的層次遍歷 II
題目[107]：給定一個二叉樹，返回其節點值自底向上的層次遍歷。 （即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）。
示例
Input: 3 / 9 20 / 15 7 Output: [[15,7], [9,20], [3]] 解題思路：使用隊列進行層次遍歷，同時記下層數，使用 map<int,vector> 記錄各個層次的節點。
struct Tuple { TreeNode *ptr; int level; Tuple(TreeNode *q = nullptr, int l = -1) : ptr(q), level(l) {} }; class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode *root) { if (root == nullptr) return vector<vector<int>>(); map<int, vector<int>> m; queue<Tuple> q; q.push(Tuple(root, 0)); while (!q.empty()) { Tuple p = q.front(); q.pop(); m[p.level].push_back(p.ptr->val); if (p.ptr->left) q.push(Tuple(p.ptr->left, p.level + 1)); if (p.ptr->right) q.push(Tuple(p.ptr->right, p.level + 1)); } vector<vector<int>> v; for (auto x : m) v.push_back(x.second); return vector<vector<int>>(v.rbegin(), v.rend()); } }; 將有序數組轉換為二叉搜索樹
題目[108]：將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。
示例
給定有序數組: [-10,-3,0,5,9], 一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹： 0 / -3 9 / / -10 5 解題思路：二叉搜索樹的性質是中序遍歷呈升序，所以數組的中間元素 nums[mid] 必然是二叉樹的根節點。所以 [start, mid - 1] 是左子樹，[mid + 1, end] 是右子樹，遞歸處理。如果數組長度為偶數，中間元素有 2 個，可任意取一個為根節點。
class Solution { public: TreeNode *sortedArrayToBST(vector<int> &nums) { TreeNode *root = nullptr; innerCreate(nums, 0, nums.size() - 1, root); return root; } void innerCreate(vector<int> &v, int start, int end, TreeNode *&p) { if (start > end) return; int mid = start + (end - start) / 2; p = new TreeNode(v[mid]); innerCreate(v, start, mid - 1, p->left); innerCreate(v, mid + 1, end, p->right); } }; 平衡二叉樹
題目[110]：給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
示例
Input: [3,9,20,null,null,15,7] 3 / 9 20 / 15 7 Output: true 解題思路：
-
暴力解法
#include <cmath> class Solution { public: bool isBalanced(TreeNode *root) { return forceSolution(root); } // brute force solution bool forceSolution(TreeNode *p) { if (p == nullptr) return true; bool flag = abs(height(p->left) - height(p->right)) <= 1; return flag && forceSolution(p->left) && forceSolution(p->right); } int height(TreeNode *p) { if (p == nullptr) return 0; return max(height(p->left), height(p->right)) + 1; } };請注意一點細節，
flag && forceSolution(p->left) && forceSolution(p->right)效率要比forceSolution(p->left) && forceSolution(p->right) && flag高。顯然，暴力解法對求高度存在需要「冗餘」的情況，比如，我們知道
h(left) = height(p->left)，那麼h(p) = h(left) + 1，但是暴力解法仍然用h(p) = height(p)。 -
自底向上的遞歸
返回值表示以
p為根的子樹是否平衡，height記錄以p為根的子樹的高度。bool isBalanced(TreeNode *root) { int height = 0; return innerIsBalanced(root, height); } bool innerIsBalanced(TreeNode *p, int &height) { if (p == nullptr) { height = 0; return true; } int lh = 0, rh = 0; if (innerIsBalanced(p->left, lh) && innerIsBalanced(p->right, rh) && abs(lh - rh) <= 1) { height = max(lh, rh) + 1; return true; } return false; }
二叉樹的最小深度
題目[111]：給定一個二叉樹，找出其最小深度。最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。
示例
Input: 3 / 9 20 / 15 7 Output: 2 解題思路：記錄每個節點層數的層次遍歷（實質上是 BFS）。第一個葉子節點的層數就是答案。
class Solution { public: int minDepth(TreeNode *root) { return (root == nullptr) ? 0 : bfs(root); } int bfs(TreeNode *root) { typedef pair<TreeNode *, int> Node; queue<Node> q; q.push(Node(root, 1)); while (!q.empty()) { auto &node = q.front(); q.pop(); if (node.first->left == nullptr && node.first->right == nullptr) return node.second; if (node.first->left != nullptr) q.push(Node(node.first->left, node.second + 1)); if (node.first->right != nullptr) q.push(Node(node.first->right, node.second + 1)); } return -1; } }; 路徑總和
題目[112]：給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等於目標和。
示例
Input: sum = 22 5 / 4 8 / / 11 13 4 / 7 2 1 Output: true, because sum(5->4->11->2) = 22 解題思路：回溯法。current 記錄當前的遍歷路徑的和。
class Solution { public: bool hasPathSum(TreeNode *root, int sum) { bool result = false; innerSum(root, sum, 0, result); return result; } void innerSum(TreeNode *p, int target, int current, bool &result) { if (p == nullptr) return; current += p->val; if (current == target && p->left == nullptr && p->right == nullptr) { result = true; return; } innerSum(p->left, target, current, result); if (!result) innerSum(p->right, target, current, result); } }; 翻轉二叉樹
題目[226]：翻轉一棵二叉樹。
示例
Input: 4 / 2 7 / / 1 3 6 9 Output: 4 / 7 2 / / 9 6 3 1 解題思路：對每個節點執行 swap(p->left, p->right) 。TreeNode* &p 表示的是指針的引用。
class Solution { public: TreeNode *invertTree(TreeNode *root) { if (root != nullptr) innerInvert(root->left, root->right); return root; } void innerInvert(TreeNode *&l, TreeNode *&r) { auto p = l; l = r; r = p; if (l != nullptr) innerInvert(l->left, l->right); if (r != nullptr) innerInvert(r->left, r->right); } }; 二叉搜索樹的最近公共祖先
題目[235]：給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先。
示例
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 輸出: 6 解釋: 節點 2 和節點 8 的最近公共祖先是 6。 解題思路：利用二叉搜索樹的性質，左子樹 < 根 < 右子樹。那麼：
p.val < root.val && q.val < root.val：在左子樹搜索。p.val > root.val && q.val < root.val：在右子樹搜索。- 其他情況：
root就是公共祖先。
遞歸解法
TreeNode *lca(TreeNode *root, TreeNode *p, TreeNode *q) { if (p->val < root->val && q->val < root->val) return lca(root->left, p, q); else if (p->val > root->val && q->val > root->val) return lca(root->right, p, q); else return root; } 非遞歸解法
TreeNode *lca2(TreeNode *root, TreeNode *p, TreeNode *q) { auto node = root; while (node != nullptr) { if (p->val < node->val && q->val < node->val) node = node->left; else if (p->val > node->val && q->val > node->val) node = node->right; else break; } return node; } 二叉樹的所有路徑
題目[257]：給定一個二叉樹，返回所有從根節點到葉子節點的路徑。
示例
輸入: 1 / 2 3 5 輸出: ["1->2->5", "1->3"] 解釋: 所有根節點到葉子節點的路徑為: 1->2->5, 1->3 解題思路：顯而易見的回溯法（實際上也是二叉樹的遍歷），如果找到葉子節點，說明是一個完整的路徑。
#include "leetcode.h" class Solution { public: vector<string> result; vector<string> binaryTreePaths(TreeNode *root) { if (root != nullptr) preorder(root, ""); return result; } void preorder(TreeNode *p, string s) { bool l = (p->left != nullptr); bool r = (p->right != nullptr); if (l || r) s += to_string(p->val) + "->"; else if (!l && !r) { s += to_string(p->val); result.push_back(s); return; } if (l) preorder(p->left, s); if (r) preorder(p->right, s); } }; 左葉子之和
題目[404]：計算給定二叉樹的所有左葉子之和。
示例
3 / 9 20 / 15 7 在這個二叉樹中，有兩個左葉子，分別是 9 和 15，所以返回 24 解題思路：遍歷過程使用一個 flag 來表示本次節點是否為左子樹。如果既是左子樹，又是葉子節點，就是要累加的節點。
#include "leetcode.h" class Solution { public: int sum = 0; int sumOfLeftLeaves(TreeNode *root) { if (root != nullptr) preorder(root, false); return sum; } void preorder(TreeNode *root, bool isLeft) { bool l = (root->left != nullptr); bool r = (root->right != nullptr); if (isLeft && !l && !r) sum += root->val; if (l) preorder(root->left, true); if (r) preorder(root->right, false); } }; ⭐ 路徑總和 III
題目[437]：給定一個二叉樹，它的每個結點都存放著一個整數值。找出路徑和等於給定數值的路徑總數。路徑不需要從根節點開始，也不需要在葉子節點結束，但是路徑方向必須是向下的（只能從父節點到子節點）。二叉樹不超過1000個節點，且節點數值範圍是 [-1000000,1000000] 的整數。
示例
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / 5 -3 / 3 2 11 / 3 -2 1 返回 3。和等於 8 的路徑有: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11 解題思路：將二叉樹的每一個完整路徑看作是一個數組 nums（假設第一個元素是 nums[1]），那麼本題就是要找到 sum(i, j) = sum 的下標 i 和 j 。
為此，使用一個數組 v ，v[0] = 0，v[i] 表示 sum(nums[1] ... nums[i]) ，即 nums 前 i 個元素的和。那麼 sum(nums[i] ... nums[j]) = v[j] - v[i - 1] 。
使用先序遍歷每一個從根到葉子的路徑。
class Solution { public: int result = 0; int pathSum(TreeNode *root, int sum) { if (root == nullptr) return 0; int d = depth(root); vector<int> v(d + 1); preorder(1, v, root, sum); return result; } int depth(TreeNode *p) { if (p == nullptr) return 0; return max(depth(p->left), depth(p->right)) + 1; } void preorder(int idx, vector<int> &v, TreeNode *p, const int sum) { if (p == nullptr) return; v[idx] = v[idx - 1] + p->val; for (int i = 0; i < idx; i++) { if (v[idx] - v[i] == sum) result++; } preorder(idx + 1, v, p->left, sum); preorder(idx + 1, v, p->right, sum); } }; ⭐二叉搜索樹中的眾數
題目[501]：給定一個有相同值的二叉搜索樹（BST），找出 BST 中的所有眾數（出現頻率最高的元素）。
示例
Input: 1 2 / 2 Output: [2] 解題思路：利用BST的性質，中序遍歷為升序序列。current 記錄當前數字 number 出現的次數，last 記錄上一次找到的「候選眾數」出現的次數。
class Solution { public: vector<int> v; int current = 0; int last = 0; int number = 0x80000000; vector<int> findMode(TreeNode *root) { if (root != nullptr) inorder(root); return v; } void inorder(TreeNode *p) { if (p == nullptr) return; inorder(p->left); if (last == 0) last = 1; if (p->val != number) current = 0; number = p->val; current++; if (current == last) v.push_back(number); if (current > last) { last = current; v.clear(), v.push_back(number); } inorder(p->right); } }; 二叉搜索樹的最小絕對差
題目[530]：給你一棵所有節點為非負值的二叉搜索樹，請你計算樹中任意兩節點的差的絕對值的最小值。
示例
輸入： 1 3 / 2 輸出：1 解釋：最小絕對差為 1，其中 2 和 1 的差的絕對值為 1（或者 2 和 3）。 解題思路：BST中序遍歷呈升序。
#include "leetcode.h" class Solution { public: int result = 0x7ffffff; int pre = 0x7fffffff; int getMinimumDifference(TreeNode *root) { inorder(root); return result; } void inorder(TreeNode *p) { if (p == nullptr) return; inorder(p->left); result = min(result, abs(p->val - pre)); pre = p->val; inorder(p->right); } }; 把二叉搜索樹轉換為累加樹
題目[538]：給定一個二叉搜索樹（Binary Search Tree），把它轉換成為累加樹（Greater Tree)，使得每個節點的值是原來的節點值加上所有大於它的節點值之和。
示例
輸入: 原始二叉搜索樹: 5 / 2 13 輸出: 轉換為累加樹: 18 / 20 13 解題思路：逆中序遍歷 BST 。
class Solution { public: int sum = 0; TreeNode *convertBST(TreeNode *root) { postorder(root); return root; } void postorder(TreeNode *p) { if (p == nullptr) return; postorder(p->right); sum += p->val; p->val = sum; postorder(p->left); } }; ⭐二叉樹的直徑
題目[534]：給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值。這條路徑可能穿過也可能不穿過根結點。
示例
Input: 1 / 2 3 / 4 5 Output: 3 解題思路：所謂直徑，就是二叉樹中任意路徑上的節點數減一。
對於二叉樹中的每個節點 node，以 node 為根的子樹，其直徑為 depth(node.left) + depth(node.right) 。
-
自頂向下的遞歸
int result = 0; int diameterOfBinaryTree(TreeNode *root) { preorder(root); return result; } int depth(TreeNode *p) { return p == nullptr ? 0 : max(depth(p->left), depth(p->right)) + 1; } void preorder(TreeNode *p) { if (p == nullptr) return; result = max(result, depth(p->left) + depth(p->right)); preorder(p->left); preorder(p->right); } -
自底向上的遞歸
顯然，對每個節點都調用一次
depth函數，有很多冗餘的遍歷。求出每個節點的高度，實際上只需要一次自底向上的遍歷。因為depth(p) = max(depth(p.left), depth(p.right)) + 1。因此可使用後序遍歷。int result = 0; int diameterOfBinaryTree(TreeNode *root) { int height = 0; bottom2top(root, height); return result; } void bottom2top(TreeNode *p, int &height) { if (p == nullptr) { height = 0; return; } int l = height, r = height; bottom2top(p->left, l); bottom2top(p->right, r); height = max(l, r) + 1; result = max(result, l + r); }
二叉樹的坡度
題目[563]：給定一個二叉樹，計算整個樹的坡度。一個樹的節點的坡度定義即為，該節點左子樹的結點之和和右子樹結點之和的差的絕對值。空結點的的坡度是0。整個樹的坡度就是其所有節點的坡度之和。
示例
輸入: 1 / 2 3 輸出: 1 解釋: 結點的坡度 2 : 0 結點的坡度 3 : 0 結點的坡度 1 : |2-3| = 1 樹的坡度 : 0 + 0 + 1 = 1 解題思路：實際上要解決的問題是怎麼求出每個子樹的和。顯然還是採取自底向上的後序遍歷。
class Solution { public: int tilt = 0; int findTilt(TreeNode *root) { int sum = 0; postorder(root, sum); return tilt; } void postorder(TreeNode *p, int &sum) { if (p == nullptr) { return; } int l = sum, r = sum; postorder(p->left, l); postorder(p->right, r); sum += p->val + l + r; tilt += abs(l - r); } }; 另一個樹的子樹
題目[572]：給定兩個非空二叉樹 s 和 t，檢驗 s 中是否包含和 t 具有相同結構和節點值的子樹。s 的一個子樹包括 s 的一個節點和這個節點的所有子孫。s 也可以看做它自身的一棵子樹。
解題思路：暴力解法。先實現 isSame(s, t) 判斷 s 和 t 是否完全相等，再遍歷 s 的每一個節點 p ，判斷 isSame(p, t) 。
class Solution { public: bool isSubtree(TreeNode *s, TreeNode *t) { if (s == nullptr) return t == nullptr; queue<TreeNode *> q; q.push(s); while (!q.empty()) { auto p = q.front(); q.pop(); if (isSame(p, t)) return true; if (p->left != nullptr) q.push(p->left); if (p->right != nullptr) q.push(p->right); } return false; } bool isSame(TreeNode *s, TreeNode *t) { if ((s == nullptr) ^ (t == nullptr)) return false; if (s == nullptr && t == nullptr) return true; return (s->val == t->val) && isSame(s->left, t->left) && isSame(s->right, t->right); } }; 
