题目描述
Given a binary tree, return the inorder traversal of its nodes’ values.
递归解题思路
- 树的遍历
- 递归版本比较简单
- 先序遍历 -》 根左右
- 中序遍历 -》 左根右
- 后序遍历 -》 左右根
- 递归遍历的时候查看当前节点是否为空即可，如果不为空，按照上述规则进行遍历
递归版本
C++代码
/**
* 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> res; // 需要一个全局变量来记录当前节点的值，最后的结果
vector<int> inorderTraversal(TreeNode* root) {
if(root != NULL){
inorderTraversal(root -> left);
res.push_back(root -> val);
inorderTraversal(root -> right);
}
return res;
}
};
非递归中序遍历解题思路
根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。 因此其处理过程如下：对于任一结点P，
- 若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
- 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
- 直到P为NULL并且栈为空则遍历结束
C++代码
/**
* 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> res;
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* node = root;
while(node != NULL || !s.empty()){
while(node != NULL){
s.push(node);
node = node -> left;
}
if(!s.empty()){
node = s.top();
res.push_back(node -> val);
s.pop();
node = node -> right;
}
}
return res;
}
};
非递归先序遍历解题思路
根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下： 因此其处理过程如下：对于任一结点P，
- 访问结点P，并将结点P入栈;
- 判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
- 直到P为NULL并且栈为空，则遍历结束。
C++代码
/**
* 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> res;
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* node = root;
while(node != NULL || !s.empty()){
while(node != NULL){
res.push_back(node -> val);
s.push(node);
node = node -> left;
}
if(!s.empty()){
node = s.top();
s.pop();
node = node -> right;
}
}
return res;
}
};
非递归后序遍历解题思路
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。参考 :
树的遍历
对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。
C++代码
struct BTNode{
BinTree* btnode;
bool isFirst = false;
};
void postOrder2(BinTree *root) //非递归后序遍历
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //表示是第一次出现在栈顶
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else//第二次出现在栈顶
{
cout<<temp->btnode->data<<"";
p=NULL;
}
}
}
}
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
C++代码
void postOrder3(BinTree *root) //非递归后序遍历
{
stack<BinTree*> s;
BinTree *cur; //当前结点
BinTree *pre=NULL; //前一次访问的结点
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<""; //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
非递归中序/先序遍历解题思路
- 首先不慌，想一想遍历的思路
- 其实很明显是一个栈来解决
- 重要的是 这个栈怎么组织
C++代码
/**
* 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> res;
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* node = s;
while(node != NULL || s.empty()){
while(node != NULL){
// res.push_back(node -> val); // 先序遍历
s.push(node);
node = node -> left;
}
if(!s.empty()){
node = s.top();
res.push_back(node -> val); // 中序遍历
s.pop();
node = node -> right;
}
}
return res;
}
};
0304解题速录
- 首先想到用栈解题
- 初始的时候 是不需要将节点压入栈的 会执行第二个判断 此时的节点是否为空
- 然后两个循环条件 第一个是栈不为空 第二个是当前节点不为空
- 注意 第一个循环的时候 一直走 走到结尾
- 第二个条件判断 仍用原来的root来做
/**
* 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) {
if(root == nullptr){
return {};
}
vector<int> res;
stack<TreeNode*> s;
//s.push(root);
while(root != nullptr || !s.empty()){
while(root){
s.push(root);
root = root -> left;
}
if(!s.empty()){
root = s.top();
s.pop();
res.push_back(root -> val);
root = root -> right;
}
}
return res;
}
};
