二叉树遍历迭代实现

淩亂°似流年 2022-05-16 12:20 207阅读 0赞

#### 写在前面 ####

> 剑指offer：二叉搜索树的第k个结点  
> 总结二叉树的前序遍历和中序遍历的迭代实现。

#### 题目要求 ####

> 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

#### 解法 ####

class Solution {
    public:
        TreeNode* KthNode(TreeNode* pRoot, int k)
        {
            if(!pRoot||k<=0) return nullptr;
            TreeNode* cur = pRoot,*res = nullptr;
            stack<TreeNode*> s;
            while(cur||!s.empty()) {
                while(cur) {
                    s.push(cur);
                    cur = cur->left;
                }
                cur = s.top();
                s.pop();
                --k;
                if(0==k) return cur;
                cur = cur->right;
            }
           return res; 
        }
    };

> 分析：  
> 二叉搜索树的中序遍历的结果就是从小到大的顺序，所以只需要中序遍历这颗二叉树，第k个遍历的节点就是第k小的节点。

#### 总结 ####

> 二叉树的前序遍历非递归实现

TreeNode* cur = root;
    stack<TreeNode*> s;
    while(cur||!s.empty()) {
        while(cur) {
            //访该节点
            visit(cur);
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        s.pop();
        cur = cur->right;
    }

> 分析：  
> 使用stack作为辅助存储。  
> 第一次遇到的节点，首先visit，再将其放进栈当中，按照前序遍历的规则继续往该节点的左子树遍历直到左子树为空。  
> 接着pop出栈顶元素该节点必然是访问顺序当中的上一个节点，此时该节点是第二次访问到，直接出栈。  
> 此时cur的左子树以及自己已经都被visit过了，此时应往cur的右子树遍历。  
> 循环往复执行以上的步骤，直到栈为空。
> 
> 二叉树中序遍历非递归实现

TreeNode* cur = root;
    stack<TreeNode*> s;
    while(cur||!s.empty()) {
        while(cur) {
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        //访问节点
        visit(cur);
        s.pop();
        cur = cur->right;
    }

> 分析：  
> 对于二叉树的遍历有一个结论：三种遍历顺序的遍历路径是一样的，只是前序遍历在第一次遇到节点的时候就访问，中序遍历则是第二次访问到该节点的时候进行访问，后序遍历则是第三次访问到该节点才进行实际的访问。  
> 所以中序遍历区别于前序遍历的唯一区别就是实际访问的顺序，把节点放入栈的过程是第一次访问到，将节点pop出栈的时候对该节点是第二次访问，按照相同的访问顺序此时是中序遍历应该实际访问的时候。所以只需要改变访问的位置即可。  
> 对于后序遍历则没有这么简单，因为节点在第三次被访问到才能实际访问，第一次和第二次访问可以区分但是第二次和第三次都是节点处于栈当中没办法简单的区分，所以需要设计一个数据结构保存该节点被访问到的次数，每次访问该计数加一，当到第三次的时候进行实际的访问。

注意：

> 对于STL的使用：  
> 因为简单的数据结构STL都提供，在做算法题或者实现简单的逻辑的时候使用STL提供的容器是非常方便和愉快的体验。但是带来的麻烦就是必须熟悉STL各类常用容器的接口和使用方法。有些细节是制作者的考虑，所以作为使用者需要注意。  
> 在STL当中queue和stack是两种容器适配器，他们封装底层的容器，使用底层的容器的接口实现上层接口。  
> stack，queue使用的是deque作为底层容器。  
> 这两者添加元素都是push()接口没有push\_back()或者push\_front()  
> stack和queue只有固定的一端才允许被外界存取，其他的位置不允许直接访问，所以没有前后之分。  
> 同时这两者也没有迭代器，只能通过push和pop进行元素的存删，通过top获取栈顶元素，通过front获取队头元素的引用。

具体接口：

> stack:  
> 常用接口：size,empty,push,pop,top  
> queue:  
> 常用接口：size,empty,front,push,pop,back  
> 队列可以直接获得队顶和队尾元素。