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

沈建明發(fā)布于2019-08-14 15:55 / 2223人閱讀

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

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

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

轉載請注明本文地址：http://systransis.cn/yun/66117.html

樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結構，用來模擬具有樹狀結構性質的數(shù)據(jù)集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點個數(shù)。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結構，用來模擬具有樹狀結構性質的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成一個...

RaoMeng 2019-08-19 11:08 評論0 收藏0
樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結構，用來模擬具有樹狀結構性質的數(shù)據(jù)集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點個數(shù)。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結構，用來模擬具有樹狀結構性質的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成一個...

PiscesYE 2019-07-30 17:45 評論0 收藏0
JS中的二叉樹遍歷

摘要：一個二叉樹的例子廣度優(yōu)先遍歷廣度優(yōu)先遍歷是從二叉樹的第一層根結點開始，自上至下逐層遍歷在同一層中，按照從左到右的順序對結點逐一訪問。有的書里將二叉樹的遍歷只講了上面三種遞歸遍歷。二叉樹是由根節(jié)點，左子樹，右子樹組成，左子樹和友子樹分別是一個二叉樹。這篇文章主要在JS中實現(xiàn)二叉樹的遍歷。一個二叉樹的例子 var tree = { value: 1, left: { ...

ghnor 2019-08-19 17:52 評論0 收藏0
數(shù)據(jù)結構-二叉樹和二叉查找樹

摘要：樹是計算機科學中經(jīng)常用到的一種數(shù)據(jù)結構數(shù)是一種非線性的數(shù)據(jù)結構以分層的方式存儲數(shù)據(jù)數(shù)被用來存儲具有層級關系的數(shù)據(jù)比如文件系統(tǒng)中的文件樹還被用來存儲有序列表本章將研究一種特殊的樹二叉樹選擇樹而不是那些基本的數(shù)據(jù)結構是因為在二叉樹上進行查找非常樹是計算機科學中經(jīng)常用到的一種數(shù)據(jù)結構. 數(shù)是一種非線性的數(shù)據(jù)結構, 以分層的方式存儲數(shù)據(jù). 數(shù)被用來存儲具有層級關系的數(shù)據(jù), 比如文件系統(tǒng)中的文...

lindroid 2019-08-23 12:15 評論0 收藏0
leetcode100 Same Tree 引發(fā)的對遍歷?算法的思考

摘要：判斷兩棵樹是否是相同題目要求傳入兩棵樹的根節(jié)點，判斷這兩棵樹是否相同此題的核心就在于如何遍歷樹。定義樹的一種自然方式是遞歸的方式。一棵樹是一些節(jié)點的集合，這個集合可以是空集。這個遍歷算法可以用于場景如，計算一個節(jié)點的高度。判斷兩棵樹是否是相同題目要求：傳入兩棵樹的根節(jié)點，判斷這兩棵樹是否相同此題的核心就在于如何遍歷樹。一旦我們解決了這個問題，題目也就迎刃而解了。下面就來介紹一下關...

cyrils 2019-08-14 17:52 評論0 收藏0