标签：node 遍历 cur 迭代 st 二叉树 节点

1.理论基础

图源:代码随想录

满二叉树:

 

 

 

 

也可以说深度为k，有2^k-1个节点的二叉树。

完全二叉树

 

 

 二叉搜索树

 

 

 若它的左子树不空,则左子树上所有结点的值均小于它根节点的值

 若右子树不空,这右子树上所有结点的值均大于他根节点的值

其左右子树 都分别为二叉排序树

平衡二叉搜索树

AVL树,两个子树的高度差的绝对值不会超过一,而且左右两个子树是一颗平衡二叉树.

 

 

 

 

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，

所以map、set的增删操作时间时间复杂度是logn，

注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。

所以unordered比普通版本的要更快

 

存储方式:顺序存储,链式存储.

 

2.递归遍历

看到题目的第一想法:做过n次了,已经熟练的快要背下来了...

题目链接:

https://leetcode.cn/problems/binary-tree-preorder-traversal/

https://leetcode.cn/problems/binary-tree-inorder-traversal/

https://leetcode.cn/problems/binary-tree-postorder-traversal/

不做过多记录...

 

3.迭代遍历

中序,后序

看到题目的第一想法:用栈实现前序遍历能够独立的想出来当时中序和后序没有思路

看完代码随想录的想法:在遍历到叶子节点的时候判断下一个是否为空

1.当进行到左叶子节点的时候 会回溯到上一个子树根节点 然后放入右叶子节点

2.右叶子节点 结束之后 因为栈里已经没有节点了就返回到上个子树的根节点

代码实现:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

View Code

看到题目的第一想法:先序遍历:中左右->中右左->左右中

 

4.统一迭代遍历

 看到题目的第一想法:说实话,没有想法,因为之前没有做过这种所以说基本上可以说没有思路

看完代码随想录的想法:一开始明白不了,后面自己模拟了一次这个过程之后就知道怎么写了.也学会了怎么使用标记法

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};

学习时间:一个小时左右,写完就去约会了....真的好累

 

 

 

 

 

标签：node,遍历,cur,迭代,st,二叉树,节点
From： https://www.cnblogs.com/Liebelingszouxiang/p/17137174.html