二叉树遍历算法收集(先序 preorder，后序 postorder，中序 inorder）循环+

沈建明发布于2019-08-14 15:55 / 2183人阅读

摘要：指的是的位置。算法比较简单，算法比较难想，可是原题都说了

preorder: root-left-right
inorder: left-root-right
postorder: left-right-root

order指的是root的位置。

recursive算法比较简单，iterative算法比较难想，可是leetcode原题都说了： recursive method is trivial, could you do iteration?

144.Binary Tree Preorder Traversal

/*iterative*/
public List preorderTraversal(TreeNode root) {
    List result = new LinkedList<>();
    if(root == null) return result;
    Stack stack = new Stack<>();
    stack.push(root);
    TreeNode n = root;
    while(!stack.isEmpty()){
        n = stack.pop();
        result.add(n.val);
        if(n.right!= null) stack.push(n.right);
        if(n.left != null) stack.push(n.left);
    }
    return result;
}

/*recursive*/
public List preorderTraversal(TreeNode root) {
    List result = new LinkedList<>();
    preHelper(root,result);
    return result;
}

private void preHelper(TreeNode n, List result){
    if(n == null) return;
    result.add(n.val);
    if(n.left != null) preHelper(n.left,result);
    if(n.right!= null) preHelper(n.right,result);
}

94.Binary Tree Inorder Traversal

/*iterative*/
public List inorderTraversal(TreeNode root) {
    List result = new LinkedList<>();
    TreeNode curr =root;
    Stack stack = new Stack<>();
    
    while(curr!=null || !stack.isEmpty()){
        while(curr!=null){
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

/* recursive*/
public List inorderTraversal(TreeNode root) {
    List result = new LinkedList<>();
    inHelper(root,result);
    return result;
}
private void inHelper(TreeNode n, List result){
    if(n == null) return;
    if(n.left!=null) inHelper(n.left,result);
    result.add(n.val);
    if(n.right != null) inHelper(n.right,result);
}

145.Binary Tree Postorder Traversal

/*iterative*/ 
public List postorderTraversal(TreeNode root) {
    LinkedList result = new LinkedList<>();
    if(root == null) return result;
    TreeNode curr = root;
    Stack stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()){
        curr = stack.pop();
        result.addFirst(curr.val);
        if(curr.left != null)
            stack.push(curr.left);
        if(curr.right != null)
            stack.push(curr.right);
    }
    return result;
}

/*recursive*/
public List postorderTraversal(TreeNode root) {
    List result = new LinkedList<>();
    postHelper(root,result);
    return result;
}

private void postHelper(TreeNode n, List result){
    if(n == null) return;
    if(n.left != null) postHelper(n.left,result);
    if(n.right!= null) postHelper(n.right,result);
    result.add(n.val);
}

云服务器 GPU云服务器二叉树遍历二叉树的遍历 JS二叉树遍历非递归二叉树遍历

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66117.html

树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

RaoMeng 2019-08-19 11:08 评论0 收藏0
树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

PiscesYE 2019-07-30 17:45 评论0 收藏0
JS中的二叉树遍历

摘要：一个二叉树的例子广度优先遍历广度优先遍历是从二叉树的第一层根结点开始，自上至下逐层遍历在同一层中，按照从左到右的顺序对结点逐一访问。有的书里将二叉树的遍历只讲了上面三种递归遍历。二叉树是由根节点，左子树，右子树组成，左子树和友子树分别是一个二叉树。这篇文章主要在JS中实现二叉树的遍历。一个二叉树的例子 var tree = { value: 1, left: { ...

ghnor 2019-08-19 17:52 评论0 收藏0
数据结构-二叉树和二叉查找树

摘要：树是计算机科学中经常用到的一种数据结构数是一种非线性的数据结构以分层的方式存储数据数被用来存储具有层级关系的数据比如文件系统中的文件树还被用来存储有序列表本章将研究一种特殊的树二叉树选择树而不是那些基本的数据结构是因为在二叉树上进行查找非常树是计算机科学中经常用到的一种数据结构. 数是一种非线性的数据结构, 以分层的方式存储数据. 数被用来存储具有层级关系的数据, 比如文件系统中的文...

lindroid 2019-08-23 12:15 评论0 收藏0
leetcode100 Same Tree 引发的对遍历?算法的思考

摘要：判断两棵树是否是相同题目要求传入两棵树的根节点，判断这两棵树是否相同此题的核心就在于如何遍历树。定义树的一种自然方式是递归的方式。一棵树是一些节点的集合，这个集合可以是空集。这个遍历算法可以用于场景如，计算一个节点的高度。判断两棵树是否是相同题目要求：传入两棵树的根节点，判断这两棵树是否相同此题的核心就在于如何遍历树。一旦我们解决了这个问题，题目也就迎刃而解了。下面就来介绍一下关...

cyrils 2019-08-14 17:52 评论0 收藏0