|
均為 Simple 難度的水題,。 題目[94]：給定一個(gè)二叉樹(shù),，返回它的中序 遍歷。 解題思路：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]：給定兩個(gè)二叉樹(shù),，編寫一個(gè)函數(shù)來(lái)檢驗(yàn)它們是否相同,。如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的,。 示例 輸入: 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]：給定一個(gè)二叉樹(shù)，檢查它是否是鏡像對(duì)稱的,。 示例 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]：給定一個(gè)二叉樹(shù)，找出其最大深度,。二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù),。 示例 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,，因?yàn)楹暾归_(kāi)后就會(huì)執(zhí)行 4 次 DFS 。 題目[107]：給定一個(gè)二叉樹(shù),，返回其節(jié)點(diǎn)值自底向上的層次遍歷,。 （即按從葉子節(jié)點(diǎn)所在層到根節(jié)點(diǎn)所在的層，逐層從左向右遍歷）,。 示例 Input:
3
/ 9 20
/ 15 7
Output:
[[15,7], [9,20], [3]]
解題思路：使用隊(duì)列進(jìn)行層次遍歷,，同時(shí)記下層數(shù)，使用 map<int,vector> 記錄各個(gè)層次的節(jié)點(diǎn),。 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]：將一個(gè)按照升序排列的有序數(shù)組,，轉(zhuǎn)換為一棵高度平衡二叉搜索樹(shù)。本題中,，一個(gè)高度平衡二叉樹(shù)是指一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1,。 示例 給定有序數(shù)組: [-10,-3,0,5,9],
一個(gè)可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個(gè)高度平衡二叉搜索樹(shù)：
0
/ -3 9
/ /
-10 5
解題思路：二叉搜索樹(shù)的性質(zhì)是中序遍歷呈升序,，所以數(shù)組的中間元素 nums[mid] 必然是二叉樹(shù)的根節(jié)點(diǎn),。所以 [start, mid - 1] 是左子樹(shù)，[mid 1, end] 是右子樹(shù),，遞歸處理,。如果數(shù)組長(zhǎng)度為偶數(shù)，中間元素有 2 個(gè),，可任意取一個(gè)為根節(jié)點(diǎn),。 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]：給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù),。 示例 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;
}
};
請(qǐng)注意一點(diǎn)細(xì)節(jié),，flag && forceSolution(p->left) && forceSolution(p->right) 效率要比 forceSolution(p->left) && forceSolution(p->right) && flag 高。 顯然,，暴力解法對(duì)求高度存在需要「冗余」的情況,，比如，我們知道 h(left) = height(p->left)，那么 h(p) = h(left) 1,，但是暴力解法仍然用 h(p) = height(p) ,。 自底向上的遞歸 返回值表示以 p 為根的子樹(shù)是否平衡，height 記錄以 p 為根的子樹(shù)的高度,。 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]：給定一個(gè)二叉樹(shù),，找出其最小深度。最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量,。 示例 Input:
3
/ 9 20
/ 15 7
Output: 2
解題思路：記錄每個(gè)節(jié)點(diǎn)層數(shù)的層次遍歷（實(shí)質(zhì)上是 BFS）,。第一個(gè)葉子節(jié)點(diǎn)的層數(shù)就是答案。 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]：給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和,，判斷該樹(shù)中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑,，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和。 示例 Input: sum = 22
5
/ 4 8
/ / 11 13 4
/ \ 7 2 1
Output: true, because sum(5->4->11->2) = 22
解題思路：回溯法,。current 記錄當(dāng)前的遍歷路徑的和,。 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]：翻轉(zhuǎn)一棵二叉樹(shù)。 示例 Input:
4
/ 2 7
/ \ / 1 3 6 9
Output:
4
/ 7 2
/ \ / 9 6 3 1
解題思路：對(duì)每個(gè)節(jié)點(diǎn)執(zhí)行 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]：給定一個(gè)二叉搜索樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。 示例 輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6
解釋: 節(jié)點(diǎn) 2 和節(jié)點(diǎn) 8 的最近公共祖先是 6,。
解題思路：利用二叉搜索樹(shù)的性質(zhì),，左子樹(shù) < 根 < 右子樹(shù),。那么： 遞歸解法 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]：給定一個(gè)二叉樹(shù),，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。 示例 輸入:
1
/ 2 3
5
輸出: ["1->2->5", "1->3"]
解釋: 所有根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑為: 1->2->5, 1->3
解題思路：顯而易見(jiàn)的回溯法（實(shí)際上也是二叉樹(shù)的遍歷）,，如果找到葉子節(jié)點(diǎn),，說(shuō)明是一個(gè)完整的路徑。 #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]：計(jì)算給定二叉樹(shù)的所有左葉子之和,。 示例 3
/ 9 20
/ 15 7
在這個(gè)二叉樹(shù)中,，有兩個(gè)左葉子，分別是 9 和 15,，所以返回 24
解題思路：遍歷過(guò)程使用一個(gè) flag 來(lái)表示本次節(jié)點(diǎn)是否為左子樹(shù),。如果既是左子樹(shù)，又是葉子節(jié)點(diǎn),，就是要累加的節(jié)點(diǎn),。 #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);
}
};
題目[437]：給定一個(gè)二叉樹(shù)，它的每個(gè)結(jié)點(diǎn)都存放著一個(gè)整數(shù)值。找出路徑和等于給定數(shù)值的路徑總數(shù),。路徑不需要從根節(jié)點(diǎn)開(kāi)始,，也不需要在葉子節(jié)點(diǎn)結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）,。二叉樹(shù)不超過(guò)1000個(gè)節(jié)點(diǎn),，且節(jié)點(diǎn)數(shù)值范圍是 [-1000000,1000000] 的整數(shù)。 示例 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
解題思路：將二叉樹(shù)的每一個(gè)完整路徑看作是一個(gè)數(shù)組 nums（假設(shè)第一個(gè)元素是 nums[1]）,，那么本題就是要找到 sum(i, j) = sum 的下標(biāo) i 和 j 。 為此,，使用一個(gè)數(shù)組 v ,，v[0] = 0，v[i] 表示 sum(nums[1] ... nums[i]) ,，即 nums 前 i 個(gè)元素的和,。那么 sum(nums[i] ... nums[j]) = v[j] - v[i - 1] 。 使用先序遍歷每一個(gè)從根到葉子的路徑,。 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]：給定一個(gè)有相同值的二叉搜索樹(shù)（BST）,，找出 BST 中的所有眾數(shù)（出現(xiàn)頻率最高的元素）。 示例 Input:
1
2
/
2
Output: [2]
解題思路：利用BST的性質(zhì),，中序遍歷為升序序列,。current 記錄當(dāng)前數(shù)字 number 出現(xiàn)的次數(shù)，last 記錄上一次找到的「候選眾數(shù)」出現(xiàn)的次數(shù),。 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]：給你一棵所有節(jié)點(diǎn)為非負(fù)值的二叉搜索樹(shù),，請(qǐng)你計(jì)算樹(shù)中任意兩節(jié)點(diǎn)的差的絕對(duì)值的最小值。 示例 輸入：
1
3
/
2
輸出：1
解釋：最小絕對(duì)差為 1,，其中 2 和 1 的差的絕對(duì)值為 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]：給定一個(gè)二叉搜索樹(shù)（Binary Search Tree）,，把它轉(zhuǎn)換成為累加樹(shù)（Greater Tree),，使得每個(gè)節(jié)點(diǎn)的值是原來(lái)的節(jié)點(diǎn)值加上所有大于它的節(jié)點(diǎn)值之和。 示例 輸入: 原始二叉搜索樹(shù):
5
/ 2 13
輸出: 轉(zhuǎn)換為累加樹(shù):
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]：給定一棵二叉樹(shù),，你需要計(jì)算它的直徑長(zhǎng)度。一棵二叉樹(shù)的直徑長(zhǎng)度是任意兩個(gè)結(jié)點(diǎn)路徑長(zhǎng)度中的最大值,。這條路徑可能穿過(guò)也可能不穿過(guò)根結(jié)點(diǎn),。 示例 Input:
1
/ 2 3
/ \
4 5
Output: 3
解題思路：所謂直徑，就是二叉樹(shù)中任意路徑上的節(jié)點(diǎn)數(shù)減一,。 對(duì)于二叉樹(shù)中的每個(gè)節(jié)點(diǎn) node,，以 node 為根的子樹(shù),，其直徑為 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);
}
自底向上的遞歸 顯然,，對(duì)每個(gè)節(jié)點(diǎn)都調(diào)用一次 depth 函數(shù),，有很多冗余的遍歷。求出每個(gè)節(jié)點(diǎn)的高度,，實(shí)際上只需要一次自底向上的遍歷,。因?yàn)?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]：給定一個(gè)二叉樹(shù),，計(jì)算整個(gè)樹(shù)的坡度。一個(gè)樹(shù)的節(jié)點(diǎn)的坡度定義即為,，該節(jié)點(diǎn)左子樹(shù)的結(jié)點(diǎn)之和和右子樹(shù)結(jié)點(diǎn)之和的差的絕對(duì)值,。空結(jié)點(diǎn)的的坡度是0,。整個(gè)樹(shù)的坡度就是其所有節(jié)點(diǎn)的坡度之和,。 示例 輸入:
1
/ 2 3
輸出: 1
解釋:
結(jié)點(diǎn)的坡度 2 : 0
結(jié)點(diǎn)的坡度 3 : 0
結(jié)點(diǎn)的坡度 1 : |2-3| = 1
樹(shù)的坡度 : 0 0 1 = 1
解題思路：實(shí)際上要解決的問(wèn)題是怎么求出每個(gè)子樹(shù)的和。顯然還是采取自底向上的后序遍歷,。 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]：給定兩個(gè)非空二叉樹(shù) s 和 t,，檢驗(yàn) s 中是否包含和 t 具有相同結(jié)構(gòu)和節(jié)點(diǎn)值的子樹(shù)。s 的一個(gè)子樹(shù)包括 s 的一個(gè)節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的所有子孫,。s 也可以看做它自身的一棵子樹(shù),。 解題思路：暴力解法。先實(shí)現(xiàn) isSame(s, t) 判斷 s 和 t 是否完全相等,，再遍歷 s 的每一個(gè)節(jié)點(diǎn) 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);
}
};
來(lái)源：https://www./content-4-673101.html
|
