二叉树的中序遍历(非递归)

红太狼 2023-05-31 07:25 124阅读 0赞

** 二叉树的中序遍历**

> **题目描述: **
> 
> **中序遍历**(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
> 
> 给定一个二叉树，返回它的中序遍历。
> 
> 示例:
> 
> 输入: \[1,null,2,3\]  
>    1  
>     \\  
>      2  
>     /  
>    3
> 
> 输出: \[1,3,2\]
> 
> 来源：力扣（LeetCode）  
> **[OJ链接][OJ]**
> 
> **相关:**  
> [二叉树的前序遍历(非递归)][Link 1]  
> [二叉树的后序遍历(非递归)][Link 2]  
> [二叉树的层序遍历(非递归)][Link 3]
> 
> **分析 :**
> 
> 非递归中序遍历只需要将左孩子入栈, 直到没有左孩子时出栈, 再从其右孩子开始重复前面的操作, 上代码:

class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int> res;
            stack<TreeNode*> s;
    	while (root) {
    	    for (; root; root = root->left) {
    		s.push(root);
    	    }
    	    do {
    		root = s.top();
    		res.push_back(root->val);
    		s.pop();
    	    } while (!root->right && !s.empty());
    	    root = root->right;
    	}
    	return res;
        }
    };

提交记录 :

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70][]

[OJ]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal
[Link 1]: https://blog.csdn.net/qq_41071068/article/details/102710707
[Link 2]: https://blog.csdn.net/qq_41071068/article/details/102711278
[Link 3]: https://blog.csdn.net/qq_41071068/article/details/102711504
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: /images/20230531/8eac3c143c2c4dd5ad4ba4b14a24d178.png