深度优先遍历的三种方式:
?
中序遍历,前序遍历, 后序遍历
中序遍历:
先遍历最左边的叶节点,然后遍历其根节点,再去遍历右节点.
在图中,从1开始,往左下方2,往左下方4.这时候空了,所以回到2,再去2的右边,到5,到7,回到5,到8,这时候回到1,再去3,去6
所以顺序为: 4 ->2 ->7 ->5 ->8 ->1 ->3 ->6
递归的实现,有递归和非递归/迭代的两种方式,其中,迭代的方式相对简单,因为其实遍历的过程,就是左边中间右边的重复顺序,所以,想到用递归的思路还是很直接的.
c++代码如下
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void inorder(TreeNode* node, vector<int>& ans)
{
if(!node)
return;
inorder(node->left,ans);
ans.push_back(node->val);
inorder(node->right,ans);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root,res);
return res;
}
};如果不采用递归的思路,而是迭代的思路,那么,我们就要去维护一个数据结构,来存储遍历到的节点,这里思考一下我们对于这个数据结构的需求,在从根节点的遍历过程中,一旦我们访问到左节点,我们就应该把它放到这个数据结构中,这里考虑到用stack的数据结构,因为后遍历到的应该首先被存进去. 此外,中序遍历迭代方法的难点在于, 我们将一个元素存入stack,和我们调用它,是两个步骤,比如根节点在最开始就被存储了,但实际上,他是在后面才被调用,因此实现起来会感到不适.
我们要思考几个问题
1. 什么时候把节点存入stack,nullptr该怎么处理
2. 什么时候去遍历右边
3.什么时候把右边的元素存进去
二叉树的迭代中序遍历实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> NodeStack;
//为什么这里有两个条件?即使root指向nullptr,
//我们也要处理,这时候要处理的是top
while(root||!NodeStack.empty())
{
while(root)
{
NodeStack.push(root);
root=root->left;
}
root = NodeStack.top();
NodeStack.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
};完全二叉树的判断