BinaryTree 迭代层序遍历

5 October 2024   1317 words   ~3 mins
#binaryTree #cpp

二叉树的迭代遍历法（基于栈实现）

题目链接

前序遍历法

不通过递归来实现二叉树的遍历，就需要一种数据结构能够记录我们的遍历顺序，并能按照某种顺序输出。

其中栈便是一种实现这种功能的数据结构，遵循着FILO规则我们可以轻易想到如果按照 右 左 前 的顺序放入栈，那么再依次弹出即可。

但是我们知道，这里的 右 左 内部都包含这各自的 右 左 前，要想全部装填好后再弹出是不现实的，只能一边弹出一边填入。

因为是前序遍历，所以我们可以在装入stack后立即弹出加入res数组，接着将 右 左 ,装入stack，这时我们就需要将 左 看作完整树，那么重复上述步骤，弹出元素，将这个节点的 右 左 装入stack。

我们可以写出如下代码

vector<int> preorderTraversal(TreeNode* root) {
        std::stack<TreeNode*> st;
	    std::vector<int> res;
	    if(root != nullptr ) st.push(root); //将 `前` 加入
	    while(!st.empty()){
            root = st.top();//选择最后一个元素
            res.push_back(root->val); //进入res数组
            st.pop(); //弹出
            if (root->right != nullptr)
            {
                st.push(root->right);
            }
            if (root->left != nullptr)
            {
                st.push(root->left);
            }

        }
        return res;
    }

前序遍历的迭代方式是最简单理解的，其他中序后序难度相较其稍高，需要多理解找出相似点与不同点。

中序遍历法

我们知道前序遍历会沿着左侧方向不断遍历直到为空，此时回到父节点，然后再进入右子树，向左不断遍历，如图所示。

我们可以根据这个图来写基本的框架

while !root or !st.empty() 
    while root is not Null  
    //这里对应1， 将当前树的所有左节点加入栈
        st.push(root)
        root = root->left
//此时已全部加入，开始返回加入res数组，并将右子树加入栈
    root = st.top()
    res.push(root->val)
    st.pop()
    root = root->right

我们可以写出如下代码

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        std::stack<TreeNode*> st;
	    std::vector<int> res;
       while(root != nullptr || !st.empty()){
	    while(root != nullptr){
            st.push(root);
            root = root->left;
        }
            root = st.top();
            st.pop();
            res.push_back(root->val);
            root = root->right;

       }

        return res;
    }
};

后序遍历法

后序遍历法我们可以参照中序遍历法，在其基础上修改。

while !root or !st.empty() 
    while root is not Null  
        st.push(root)
        root = root->left
        
    root = st.top()
    res.push(root->val)
    st.pop()
    root = root->right

仔细观察代码，我们可以发现，如果想实现后序遍历 while root is not Null 这一块不需要改变，我们应该要先去遍历右子树，最后才能将当前节点加入到res。

我们发现当左节点访问完要先访问右节点有如下几种情况：

  1. 右节点存在，且未被访问
  2. 右节点存在，且已被访问
  3. 右节点不存在

其中便引出了第二点与中序不同的点，我们需要判断这个右节点是否被访问了，我们这里添加一个prev指针用来记录右节点是否被访问。

因为从上图中我们可以看出只有右节点访问完成后，返回父节点，此时才会遇到右节点存在，且已被访问的情况，所以我们只需要记录上一个节点即可。

2. 3.
if root->right == null or root->right == prev
	//右节点不存在           存在且被访问
	res.push_back(root->val)
    prev = root
    root = nullptr

这里有一点我们需要注意，那就是最后将root赋值为nullptr,此时如果不这样赋值，就会再次进入将左节点加入栈的循环。当然我们可以利用prev指针来避免，但是我们尽量少修原代码。

1.
else
	st.push(root)
	root = root->right

最后完整实现代码

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        std::stack<TreeNode*> st;
	    std::vector<int> res;
	    TreeNode* prev = nullptr;
       while(root != nullptr || !st.empty()){
	    while(root != nullptr){
            st.push(root);
            root = root->left;
        }
            root = st.top();
            st.pop(); 
            if(root->right == nullptr || root->right == prev){
				res.push_back(root->val);
    			prev = root;
    			root = nullptr;
		}
			else{
			st.push(root);
			root = root->right;
		}
      }

        return res;
    }
};

当然，后序遍历还有一种简单的办法，就是在前序遍历的基础上将结果反转，不过这样就失去了这道题的意义。

后序遍历的另一种实现

vector<int> postorderTraversal(TreeNode* root) {
      std::stack<TreeNode*> st;
	    std::vector<int> res;
	    if(root != nullptr ) st.push(root);
	    while(!st.empty()){
            auto temp = st.top();
            res.push_back(temp->val);
            st.pop();
            if (temp->left != nullptr)
            {
                st.push(temp->left);
            }
            if (temp->right != nullptr)
            {
                st.push(temp->right);
            }

        }
        reverse(res.begin(), res.end());
        return res;
    }

递归实现

因为递归实现比较简单，所以不作讲解，只列出代码。

class Solution {
public:
	void dfs(TreeNode* root, vector<int>& res){
		if(root != nullptr){
			dfs(root->left, res);
                        res.push_back(root->val);
			dfs(root->right, res);
            //只需要调整顺序就可以实现前中后序遍历
		}
		
	}
    vector<int> inorderTraversal(TreeNode* root) {
    	vector<int> res;
    	if(root == nullptr) return res;
    	dfs(root, res);
    	return res;
    }
};
← prev next →