竹丝码迹

  • 首页
  • 技术分享
    • 流媒体音视频
    • Note
    • Technology
    • System
    • Code
    • Toys
  • 友情链接
    • LeetCode
    • OSCHINA
    • 牛客网
  • 关于博主
纸上得来终觉浅,绝知此事要躬行
  1. 首页
  2. Note
  3. 正文

二叉树的遍历

2020年1月12日 232点热度 1人点赞 0条评论

二叉树的遍历

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

方法一

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

        return ret;
    }
};

方法二

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root == NULL) return ret;
        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            ret.push_back(node->val); // 记录先序遍历结果
            if (node->right) s.push(node->right);
            if (node->left) s.push(node->left);
        }
        return ret;
    }
};

中序遍历(非递归)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root == NULL) return ret;

        stack<TreeNode*> s;
        TreeNode* node = root;
        // 没有压入元素或者有未弹出的元素
        while (node || !s.empty())  {
            // 压入左子树
            while (node) {
                s.push(node);
                node = node->left;
            }
            // 弹出栈顶元素
            node = s.top();
            s.pop();
            ret.push_back(node->val); // 记录中序遍历结果
            // 进入右子树
            node = node->right;
        }
        return ret;
    }
};

中序遍历——颜色标记法

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        this.val = x;
        this.left = null;
        this.right = null;
    }
}

class ColorNode {
    TreeNode node;
    String color;
    ColorNode(TreeNode node, String color) {
        this.node = node;
        this.color = color;
    }
}
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if(root == null) return res;

    Stack<ColorNode> stack = new Stack<>();

    ColorNode colorNode = new ColorNode(root, "white");
    stack.push(colorNode);

    while(!stack.empty()) {
        colorNode = stack.pop();

        if(colorNode.color.equals("white")) {
            //RNL
            if(colorNode.node.right != null) {
                stack.push(new ColorNode(colorNode.node.right, "white"));
            }
            stack.push(new ColorNode(colorNode.node, "gray"));
            if(colorNode.node.left != null) {
                stack.push(new ColorNode(colorNode.node.left, "white"));
            }
        } else {
            res.add(colorNode.node.val);
        }
    }
    return res;
}

后序遍历(非递归)

方法一

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;  
        if(root == NULL) return ret;            
        stack<TreeNode*> s;  
        s.push(root);  
        while(!s.empty()) {  
            TreeNode *n = s.top();
            s.pop();
            ret.push_back(n->val); // 记录后续遍历的过程值

            if(n->left)  s.push(n->left);  
            if(n->right) s.push(n->right);  
        }
        reverse(ret.begin(), ret.end()); // 将ret倒置获得后序遍历结果
        return ret;
    }
};

方法二

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root == nullptr) return result;
        stack<TreeNode*> s;
        TreeNode *p = root, *r = nullptr;
        while(p || !s.empty()){
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top();
            if (p->right && p->right != r) { //考虑栈顶结点的右子树结点。存在且没被访问过,将右子树结点压入栈中
                p = p->right;
            } else {
                s.pop();
                result.push_back(p->val);
                r = p;
                p = nullptr;
                //p置空作用在于当原栈顶结点被访问并弹出后,下一层while是将当前栈顶结点的左子树入栈,当前栈顶结点的左子树已经被遍历过,     
            //因此会造成死循环,所以将p置空,直接考虑当前栈顶结点的右子树
            }
        }
        return result;
    }
};
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root == nullptr) return result;
        stack<TreeNode*> s;
        TreeNode *p = root, *r = nullptr;
        while(p || !s.empty()){
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top();
            if (p->right && p->right != r) {
                p = p->right;
            } else {
                s.pop();
                result.push_back(p->val);
                r = p;
                p = nullptr;
            }
        }
        return result;
    }
};

层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > ret;
        if (!root) return ret;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int count = q.size();
            ret.push_back(vector<int>() );
            for (int i = 1; i <= count; ++i) { // 遍历当前层所有结点,并将其孩子结点入队
                TreeNode* node = q.front();
                q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return ret;
    }
};
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2020年10月13日

ronnie

这个人很懒,什么都没留下

点赞
< 上一篇
下一篇 >
最新 热点 随机
最新 热点 随机
H264基础 YUV入门基础 编解码基础 WebRTC入门 Bat脚本基础入门 只需三步便可下载无水印图片
WebRTC入门H264基础多线程与多进程STL简记C++学习历程基于C语言的Socket编程
树状数组模板 二叉树的遍历 基于C语言的Socket编程 搜索 题解代码 HZOJ_354 Coins题解
分类目录
标签聚合
树状数组 素数 动态规划 离散化 单调队列 数学 多重背包 编解码 SPFA 操作系统 分治 归并排序 贪心 WebRTC
目录
  • 1 二叉树的遍历
    • 1.1 二叉树的前序遍历(非递归)
      • 1.1.1 方法一
      • 1.1.2 方法二
    • 1.2 中序遍历(非递归)
    • 1.3 中序遍历——颜色标记法
    • 1.4 后序遍历(非递归)
      • 1.4.1 方法一
      • 1.4.2 方法二
      • 1.4.3 层序遍历

COPYRIGHT © 2021 竹丝码迹. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

黑ICP备19006658号