二叉樹遍歷算法收集(先序 preorder，后序 postorder，中序 inorder）循環+

沈建明發布于2019-08-14 15:55 / 2219人閱讀

摘要：指的是的位置。算法比較簡單，算法比較難想，可是原題都說了

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二叉樹遍歷非遞歸二叉樹遍歷

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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