1. Binary Tree Preorder Traversal
Description
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
2
/
3
Output: [1,2,3]
Analysis
- 實(shí)際就是二叉樹的先序遍歷，先序?qū)?yīng)得是根節(jié)點(diǎn)的訪問順序。
- leetcode上樹節(jié)點(diǎn)的定義如下
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
- 利用棧的思想，壓入根節(jié)點(diǎn)，訪問值，退棧，壓入左右子節(jié)點(diǎn)，訪問棧頂，退棧頂。直到棧為空。
Solution
// 使用棧記錄訪問過程中得節(jié)點(diǎn)指針，首先壓棧根節(jié)點(diǎn)，訪問該節(jié)點(diǎn)數(shù)據(jù)，后退棧，再將其右左節(jié)點(diǎn)壓棧。
// 不斷訪問棧頂后后退棧頂，直到棧為空。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode *> s;
if(root!=nullptr)
s.push(root);
while(!s.empty())
{
TreeNode* p = s.top();
result.push_back(p->val);
s.pop();
if(p->right!=nullptr)
s.push(p->right);
if(p->left!=nullptr)
s.push(p->left);
}
return result;
}
};
2.Binary Tree Inorder Traversal
Description
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
2
/
3
Output: [1,3,2]
Analysis
- 實(shí)際就是二叉樹的中序遍歷
- 不斷的壓入根左左左左，直到?jīng)]有左節(jié)點(diǎn)（即找到最左邊的節(jié)點(diǎn)）。
Solution
// 從根節(jié)點(diǎn)開始不斷壓入根左左左左，直到?jīng)]有左節(jié)點(diǎn)，訪問。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode *> s;
TreeNode* p = root;
while(!s.empty() || p!=nullptr)
{
if(p!=nullptr)
{
s.push(p);
p = p->left;
}
else
{
// 最左邊的節(jié)點(diǎn)
p = s.top();
s.pop();
result.push_back(p->val);
// 最關(guān)鍵
p = p->right;
}
}
return result;
}
};
3.Binary Tree Postorder Traversal
Description
Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
2
/
3
Output: [3,2,1]
Analysis
- 二叉樹后序遍歷
- 此題有難度，需要考慮右子樹的存在
Solution
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> s;
TreeNode *p=root, *q = nullptr;
do
{
// 不斷往左下走
while(p!=nullptr)
{
s.push(p);
p = p->left;
}
q = nullptr;
while(!s.empty())
{
p = s.top();
s.pop();
// 如果此時(shí)這個(gè)棧頂節(jié)點(diǎn)不存在右節(jié)點(diǎn)，或者已經(jīng)被訪問，則訪問他
if(p->right == q)
{
result.push_back(p->val);
// 保存剛剛訪問的節(jié)點(diǎn)
q = p;
}
// 否則的話，該節(jié)點(diǎn)還不能訪問，重新進(jìn)站，先訪問其右子樹
else
{
s.push(p);
p = p->right;
break;
}
}
}while(!s.empty());
return result;
}
};
總結(jié)
- 二叉樹的三種遍歷方式是二叉樹算法的前提。
- 二叉樹三種遍歷方法最簡(jiǎn)單的是用遞歸地方式，如下
// 先序
void preorder(TreeNode *root)
{
if(root!=nullptr)
{
visit(root);
preorder(root->left);
preorder(root->right);
}
}
// 中序
void inorder(TreeNode *root)
{
if(root!=nullptr)
{
inorder(root->left);
visit(root);
inorder(root->right);
}
}
// 后序
void postorder(TreeNode *root)
{
if(root!=nullptr)
{
postorder(root->left);
postorder(root->right);
visit(root);
}
}
- 遞歸方式很簡(jiǎn)單，所以要學(xué)會(huì)使用?；蚓€索二叉樹寫這三種遍歷。
4. Binary Tree Level Order Traversal
Description
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
Analysis
- 二叉樹的層序遍歷，層序遍歷是二叉樹的廣度優(yōu)先搜索方式，先后中遍歷都是二叉樹的深度優(yōu)先搜索方式。
- 建立一個(gè)queue，然后先把根節(jié)點(diǎn)放進(jìn)去，這時(shí)候找根節(jié)點(diǎn)的左右兩個(gè)子節(jié)點(diǎn)，這時(shí)候去掉根節(jié)點(diǎn)，此時(shí)queue里的元素就是下一層的所有節(jié)點(diǎn)，用一個(gè)for循環(huán)遍歷它們，然后存到一個(gè)一維向量里，遍歷完之后再把這個(gè)一維向量存到二維向量里，以此類推，可以完成層序遍歷。
- 比較復(fù)雜的是需要將每層數(shù)分開
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > res;
if (root == NULL) return res;
// 建立隊(duì)列
queue<TreeNode*> q;
// 根節(jié)點(diǎn)先入隊(duì)
q.push(root);
while (!q.empty()) {
// 當(dāng)前層值得容器
vector<int> oneLevel;
int size = q.size();
for (int i = 0; i < size; ++i) {
TreeNode *node = q.front();
q.pop();
oneLevel.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res.push_back(oneLevel);
}
return res;
}
};
5. Same Tree
Description
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Analysis
- 判斷兩個(gè)二叉樹是否相同，必須樹結(jié)構(gòu)和相應(yīng)得節(jié)點(diǎn)值都相同。
- 樹結(jié)構(gòu)相同，就是比較是否一個(gè)這個(gè)地方有節(jié)點(diǎn)，一個(gè)這個(gè)地方無節(jié)點(diǎn)。
- 采用遞歸得想法，分成三種情況： 如果兩個(gè)位置都是空，則是相同，如果一個(gè)空一個(gè)非空，則不同，最后根節(jié)點(diǎn)，左子樹，右子樹三方判斷合并。
Solution
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
// 如果兩個(gè)樹都是空，則是相同
if(!p && !q)
return true;
// 如果一個(gè)空一個(gè)非空
if(!p || !q)
return false;
// 根節(jié)點(diǎn)，左子樹，右子樹三方判斷合并
return (p->val==q->val) && (isSameTree(p->left, q->left))
&& (isSameTree(p->right, q->right));
}
};
6. Symmetric Tree
Decription
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
Analysis
- 判斷一棵樹是否是對(duì)稱的。思路和判斷兩棵樹是否是相同的很類似。都是遞歸的思想，區(qū)別是，這里因?yàn)槭且豢脴洌孕枰瓤紤]根節(jié)點(diǎn)。后面三方合并的地方，判斷兩棵樹相同是同時(shí)遞歸做作，右右。判斷一棵樹是否對(duì)稱，應(yīng)該遞歸左右，右左。
Solution
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root)
return true;
else
return isSymmetric(root->left, root->right);
}
bool isSymmetric(TreeNode *p, TreeNode *q)
{
if(!p && !q)
return true;
if(!p || !q)
return false;
return (p->val == q->val) && (isSymmetric(p->left, q->right))
&& (isSymmetric(p->right, q->left));
}
};
7. Construct Binary Tree from Preorder and Inorder Traversal
Description
Given preorder and inorder traversal of a tree, construct the binary tree.
Analysis
- 根據(jù)先序遍歷和中序遍歷結(jié)果，建立二叉樹
- 先序的順序的第一個(gè)肯定是根，所以原二叉樹的根節(jié)點(diǎn)可以知道，題目中給了一個(gè)很關(guān)鍵的條件就是樹中沒有相同元素，有了這個(gè)條件我們就可以在中序遍歷中也定位出根節(jié)點(diǎn)的位置，并以根節(jié)點(diǎn)的位置將中序遍歷拆分為左右兩個(gè)部分，分別對(duì)其遞歸調(diào)用原函數(shù)。
Solution
class Solution {
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode *buildTree(vector<int> &preorder, int pLeft, int pRight, vector<int> &inorder, int iLeft, int iRight) {
if (pLeft > pRight || iLeft > iRight) return NULL;
int i = 0;
for (i = iLeft; i <= iRight; ++i) {
if (preorder[pLeft] == inorder[i]) break;
}
TreeNode *cur = new TreeNode(preorder[pLeft]);
cur->left = buildTree(preorder, pLeft + 1, pLeft + i - iLeft, inorder, iLeft, i - 1);
cur->right = buildTree(preorder, pLeft + i - iLeft + 1, pRight, inorder, i + 1, iRight);
return cur;
}
};
8. Construct Binary Tree from Inorder and Postorder Traversal
Description
Given inorder and postorder traversal of a tree, construct the binary tree.
Analysis
- 利用中序和后序遍歷，建立二叉樹
- 中序的遍歷順序是左-根-右，后序的順序是左-右-根，對(duì)于這種樹的重建一般都是采用遞歸來做。由于后序的順序的最后一個(gè)肯定是根，所以原二叉樹的根節(jié)點(diǎn)可以知道，題目中給了一個(gè)很關(guān)鍵的條件就是樹中沒有相同元素，有了這個(gè)條件我們就可以在中序遍歷中也定位出根節(jié)點(diǎn)的位置，并以根節(jié)點(diǎn)的位置將中序遍歷拆分為左右兩個(gè)部分，分別對(duì)其遞歸調(diào)用原函數(shù)。
Solution
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
TreeNode *buildTree(vector<int> &inorder, int iLeft, int iRight, vector<int> &postorder, int pLeft, int pRight) {
if (iLeft > iRight || pLeft > pRight) return NULL;
TreeNode *cur = new TreeNode(postorder[pRight]);
int i = 0;
for (i = iLeft; i < inorder.size(); ++i) {
if (inorder[i] == cur->val) break;
}
cur->left = buildTree(inorder, iLeft, i - 1, postorder, pLeft, pLeft + i - iLeft - 1);
cur->right = buildTree(inorder, i + 1, iRight, postorder, pLeft + i - iLeft, pRight - 1);
return cur;
}
};
總結(jié)
- 二叉樹是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，基本所有題目都可以考慮遞歸的思想。
- 遞歸一定是DFS，二叉樹的先序中序后序都可以看成是DFS。
- 遞歸和迭代的區(qū)別
- 遞歸是重復(fù)調(diào)用函數(shù)自身實(shí)現(xiàn)循環(huán)。迭代是函數(shù)內(nèi)某段代碼實(shí)現(xiàn)循環(huán)
- 遞歸循環(huán)中，遇到滿足終止條件的情況時(shí)逐層返回來結(jié)束。迭代則使用計(jì)數(shù)器結(jié)束循環(huán)。
- 遞歸就是在過程或函數(shù)里面調(diào)用自身;在使用遞歸時(shí),必須有一個(gè)明確的遞歸結(jié)束條件,稱為遞歸出口.
- 迭代是逐漸逼近，用新值覆蓋舊值，直到滿足條件后結(jié)束，不保存中間值，空間利用率高。遞歸是將一個(gè)問題分解為若干相對(duì)小一點(diǎn)的問題，遇到遞歸出口再原路返回，因此必須保存相關(guān)的中間值，這些中間值壓入棧保存，問題規(guī)模較大時(shí)會(huì)占用大量?jī)?nèi)存。
9. Minimum Depth of Binary Tree
Description
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Analysis
- 判斷一棵樹的最小深度，即最快找到葉子節(jié)點(diǎn)的深度。
遞歸，若為空樹返回0；
若左子樹為空，則返回右子樹的最小深度+1；（加1是因?yàn)橐由细@一層，下同）
若右子樹為空，則返回左子樹的最小深度+1；
若左右子樹均不為空，則取左、右子樹最小深度的較小值，+1；
Solution
class Solution {
public:
int minDepth(TreeNode* root) {
// 直接遞歸，初始根節(jié)點(diǎn)是沒有brother
return minDepth(root, false);
}
int minDepth(TreeNode* p, bool hasbrother)
{
// 當(dāng)前節(jié)點(diǎn)是空節(jié)點(diǎn)
if(!p)
return hasbrother?INT_MAX:0;
// 遞歸
// 分別考慮左右子樹
return 1+min(minDepth(p->left, p->right!=NULL),
minDepth(p->right, p->left!=NULL));
}
};
10. Maximum Depth of Binary Tree
Description
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Analysis
- 不需要考慮其它，直接遞歸
Solution
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root)
return 0;
else
return 1+max(maxDepth(root->left), maxDepth(root->right));
}
};
