LeetCode--二叉树1--树的遍历
一 深度遍历
- 深度遍历里面由 三种遍历方式，两种实现方法。都要熟练掌握。
- 值得注意的是，当你删除树中的节点时，删除过程将按照后序遍历的顺序进行。
- 也就是说，当你删除一个节点时，你将首先删除它的左节点和它的右边的节点，然后再删除节点本身。
Note：后序遍历在表达式上的应用
① 用递归的方式遍历二叉树
Note：
递归的实现方式里，函数的返回值需要为void类型，否则没法进行。
所以我们需要设定一个help函数来完成递归。
后序遍历
/**
* 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 ) {
vector<int> nodes;
helper( root, nodes);
return nodes;
}
void helper(TreeNode *pnode , vector<int> &node_ids)
{
if( pnode == NULL)
{
std::cout << " The tree is null ! " << std::endl;
}
else
{
if(pnode != NULL)
helper(pnode->left,node_ids);
if(pnode != NULL)
helper(pnode->right,node_ids);
node_ids.push_back(pnode->val);
}
}
};
前序遍历
/**
* 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> preorderTraversal(TreeNode* root ) {
vector<int> nodes;
helper( root, nodes);
return nodes;
}
void helper(TreeNode *pnode , vector<int> &node_ids)
{
if( pnode == NULL)
{
std::cout << " The tree is null ! " << std::endl;
}
else
{
node_ids.push_back(pnode->val);
if(pnode != NULL)
helper(pnode->left,node_ids);
if(pnode != NULL)
helper(pnode->right,node_ids);
}
}
};
中序遍历
/**
* 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> inorderTraversal(TreeNode* root ) {
vector<int> nodes;
helper( root, nodes);
return nodes;
}
void helper(TreeNode *pnode , vector<int> &node_ids)
{
if( pnode == NULL)
{
std::cout << " The tree is null ! " << std::endl;
}
else
{
if(pnode != NULL)
helper(pnode->left,node_ids);
node_ids.push_back(pnode->val);
if(pnode != NULL)
helper(pnode->right,node_ids);
}
}
};
② 用非递归的方式遍历二叉树
用递归方式实现的问题都可以用非递归方法实现。
递归的本质就是利用函数栈来保存信息。
用自己申请的数据结构来代替函数栈，可以实现同样的功能。
①使用栈实现前序遍历：
- 申请一个栈stack，头结点入栈。
- 栈顶元素出栈，出栈元素的右节点和左节点依次入栈。
- 重复第二步，直到栈为空
/**
* 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> preorderTraversal(TreeNode* root) {
vector<int> orders;
stack<TreeNode*> nodes;
TreeNode* tmp;
if (root == NULL)
{
std::cerr << "The Tree is NULL !!!" << std::endl;
}
else
{
nodes.push(root);
while(nodes.empty()==0)
{
tmp = nodes.top();
nodes.pop();
orders.push_back(tmp->val);
if(tmp->right!=NULL)
nodes.push(tmp->right);
if(tmp->left!= NULL)
nodes.push(tmp->left);
}
}
return orders;
}
};
②使用栈实现中序遍历:
- 申请一个新的栈stack，定义一个变量 cur = root 节点
- cur入栈
- 令 cur = cur.left，重复步骤2，直到cur = NULL
- stack.pop(); 出栈的节点记为 node，输出 node.val
- 令 cur = node.right 重复2,3
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> inorder;
TreeNode* cur = root;
if(root != NULL)
{
stack<TreeNode*> kk ;
while( !kk.empty() || cur != NULL)
{
if(cur != NULL)
{
kk.push(cur);
cur = cur->left;
}
else
{
cur = kk.top();
kk.pop();
inorder.push_back(cur->val);
cur = cur->right;
}
}
}
return inorder;
}
};
二 层次遍历
其实就是逐层遍历树的结构
广度优先搜索一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。
该算法从一个根节点开始，首先访问节点本身。
然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。
当我们在树中进行广度优先搜索时，我们访问的节点的顺序是按照层序遍历顺序的。
实现有两种模板
- 以层为单位输出
- 以节点为单位输出
按层为单位过程
- 头节点入队
- 如果队列不为空，取到队列的元素个数，得知上一个循环加入队列的元素个数，也就是上一层的元素个数。for循环令上一层的元素出队列，并把其左右子树入队。
核心：
就是 while 循环里面套一个 for 循环。
.
.
.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(root == NULL)
return ans;
queue<TreeNode*> q;
q.push(root);
while( !q.empty() )
{
int num = q.size();
vector<int> cur;
for (int i = 0 ; i < num; i++)
{
TreeNode* pnode = q.front();
q.pop();
if (pnode->left != NULL)
q.push(pnode->left);
if (pnode->right != NULL)
q.push(pnode->right);
cur.push_back(pnode->val);
}
ans.push_back(cur);
}
return ans;
}
};