Leetcode 144 Binary Tree PreOrder Traversal

题目描述：

要求使用非递归实现：

代码如下(C++版本)

class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> res;
		deque<TreeNode*> stack;
		if (root == NULL)
			return res;
		stack.push_back(root);
		while (!stack.empty()) {
			TreeNode* p = stack.back();
			res.push_back(p->val);
			stack.pop_back();
			if (p->right != NULL) {
				stack.push_back(p->right);
			}
			if (p->left != NULL) {
				stack.push_back(p->left);
			}
		}
		return res;
	}
};

刚开始把前序遍历理解成了中序遍历的样子，尝试着写非递归中序遍历的代码，又low了，记得面试的时候还准备过，哎，下面吧二叉树的前序遍历、中序遍历、后序遍历在预习一遍。参考博客出处：http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

前序遍历根节点—>左分支—>y右分支思路

先访问根节点，并将根节点压栈
一直向左分支访问，直到左子树为空，并同时将访问过的节点压栈
从栈顶弹出元素，访问其右节点

代码如下：

class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> res;
		deque<TreeNode*> stack;
        TreeNode* p = root;
		while (p!=NULL||!stack.empty()) {
            while(p!=NULL){
                res.push_back(p->val);
                stack.push_back(p);
                p = p->lchild;
            }
            if(!stack.empty()) {
                p = stack.back();
                stack.pop_back();
                p = p->rchild;
            }			
		}
		return res;
	}
};

中序遍历和前序遍历类似，只是改变了根节点的访问次序

代码如下：

class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> res;
		deque<TreeNode*> stack;
        TreeNode* p = root;
		while (p!=NULL||!stack.empty()) {
            while(p!=NULL){
                stack.push_back(p);
                p = p->lchild;
            }
            if(!stack.empty()) {
                p = stack.back();
                res.push_back(p->val);
                stack.pop_back();
                p = p->rchild;
            }			
		}
		return res;
	}
};

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。下面介绍两种思路。

第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> res;
		deque<TreeNode*> stack;
        TreeNode* p = root;
		while (p!=NULL||!stack.empty()) {
            while(p!=NULL){
                stack.push_back(p);
                p = p->lchild;
            }
            if(!stack.empty()) {
                p = stack.back();
                if(p->flag){
                    p->flag = 0;
                    p = p->rchild;
                }
                else{
                    stack.pop_back();
                    res.push_back(p->val);
                    p=NULL
                }
            }	    		
		}
		return res;
	}
};

第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

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);
        }
    }    
}

Leetcode 144 Binary Tree PreOrder Traversal

相关推荐