这次要记录的是做leetbook：二叉树的经历，这是一本很小的book，所以决定用一晚上的时间做完。传送门
树的遍历
t1 二叉树的先序遍历
常规操作，简单题要做难，所以考虑用多种方法来写。
递归法
最常规的递归法，按照根->左->右的顺序来写就可以了。
class Solution {
public:
void solve(TreeNode*root, vector<int>& a) {
if(root == NULL) return;
a.push_back(root->val);
solve(root->left, a);
solve(root->right, a);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
solve(root, ans);
return ans;
}
};
迭代法
迭代法是用栈模拟递归的操作。因为栈具有先入后弹的特性，所以优先压右儿子进栈。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
st.push(root);
while(!st.empty())
{
TreeNode* tmp = st.top();st.pop();
if(tmp != NULL) ans.push_back(tmp->val);
else continue;
st.push(tmp->right);
st.push(tmp->left);
}
return ans;
}
};
t2 二叉树的中序遍历
递归法
class Solution {
public:
void solve(vector<int>& arr, TreeNode* node) {
if(node == NULL) return;
solve(arr, node->left);
arr.push_back(node->val);
solve(arr, node->right);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
solve(ans, root);
return ans;
}
};
迭代法
中序遍历的迭代实现代码最为复杂。
先序遍历代码简洁的原因是它“遍历”与“处理”的操作同步进行。先序遍历的顺序是根左右，每次先访问根节点然后将其值压入答案数组，接着去访问左右子树。
但中序遍历并不是这样。中序遍历需要首先找到左子树的底部，然后开始按左根右的顺序访问节点。即在找到左子树底部之前的遍历操作中是不含有“压入答案”这个处理步骤的。
解决这个不同步问题的方法就是用一个指针去完成遍历的任务。当它找到了左子树的底部时，就开始操作。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
TreeNode* pointer = root;
while(pointer != NULL || !st.empty())
{
//去遍历到左子树最底部
if(pointer != NULL)
{
st.push(pointer);
pointer = pointer->left;
}
//摸到最底部，开始操作
else
{
pointer = st.top();st.pop();
ans.push_back(pointer->val);
pointer = pointer->right;
}
}
return ans;
}
};
t3 二叉树的后序遍历
递归法
class Solution {
public:
void solve(vector<int>& arr, TreeNode* node) {
if(node == NULL) return;
solve(arr, node->left);
solve(arr, node->right);
arr.push_back(node->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
solve(ans, root);
return ans;
}
};
迭代法
后序遍历的迭代实现可以通过先序遍历的代码改进得到。
先序遍历的遍历顺序是根->左->右，后序遍历是左->右->根。那么首先调整先序遍历的代码，从 根->左->右改成根->右->左，然后在遍历完整棵树后翻转答案数组，这样就得到了按左->右->根顺序遍历的答案序列了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
st.push(root);
while(!st.empty())
{
TreeNode* tmp = st.top();st.pop();
if(tmp != NULL) ans.push_back(tmp->val);
else continue;
st.push(tmp->left);
st.push(tmp->right);
}
reverse(ans.begin(), ans.end());
return ans;
}
};
t4 二叉树的层序遍历
层序遍历顾名思义，一层一层的遍历。一般采用队列实现这个操作，每次对队首节点操作，将其左右子压入队，循环往复即可。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
queue<TreeNode*> que;
que.push(root);
if(root == NULL) return ans;
while(!que.empty())
{
int size = que.size();
vector<int> part;
while(size--)
{
TreeNode* node = que.front();que.pop();
part.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
ans.push_back(part);
}
return ans;
}
};
运用递归解决问题
t1 二叉树的最大深度
要求二叉树的最大深度，那么就要自顶向下的找。
如果当前遍历到空节点，直接return；如果当前节点是叶子节点，那么维护ans为当前ans值与depth值之间的最大值，如果都不是，继续递归找左右子树，每次深度+1.
class Solution {
public:
int ans = 0;
void find(TreeNode* node, int depth) {
if(node == NULL) return;
if(node->left == NULL && node->right == NULL)
ans = max(ans, depth);
find(node->left, depth + 1);
find(node->right, depth + 1);
}
int maxDepth(TreeNode* root) {
find(root, 1);
return ans;
}
};
t2 对称二叉树
判断一颗二叉树是否是轴对称的，可以用两个指针，依然是自上而下的遍历，一个往左的时候另一个就往右，如果它们的值到叶子节点都一直相等，显然这棵树就是对称的。
class Solution {
public:
bool check(TreeNode* l, TreeNode* r) {
//同时走到叶子节点，显然对称
if(l == NULL && r == NULL) return true;
//不同时走到叶子节点，不对称
if(l == NULL || r == NULL) return false;
//如果当前两指针指向的节点值相等且它们的左右子树都满足相等，则本身对称
return l->val == r->val && check(l->left, r->right) && check(l->right, r->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
t3 路径总和
依旧是递归。如果当前节点为空，那么说明整个遍历过程结束都没有达到suum，直接返回false；如果当前节点是叶子节点，则判断当前val是否等于sum值，如果是则返回true，除外直接递归遍历左右子树，返回二者之或。
值得注意的是，每次递归遍历用sum减去当前的val值，这样可以免除使用额外变量记录当前sum值的麻烦。
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(root == NULL) return false;
if(root->left == NULL && root->right == NULL) return root->val == sum;
return hasPathSum(root->left, sum - root->val) ||
hasPathSum(root->right, sum - root->val);
}
};