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

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

摘要：指的是的位置。算法比較簡(jiǎn)單，算法比較難想，可是原題都說(shuō)了

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

order指的是root的位置。

recursive算法比較簡(jiǎn)單，iterative算法比較難想，可是leetcode原題都說(shuō)了： 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);
}

云服務(wù)器 GPU云服務(wù)器二叉樹(shù)遍歷二叉樹(shù)的遍歷 JS二叉樹(shù)遍歷非遞歸二叉樹(shù)遍歷

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66117.html

相關(guān)文章

樹(shù)和樹(shù)的算法

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

RaoMeng 2019-08-19 11:08 評(píng)論0 收藏0
樹(shù)和樹(shù)的算法

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

PiscesYE 2019-07-30 17:45 評(píng)論0 收藏0
JS中的二叉樹(shù)遍歷

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

ghnor 2019-08-19 17:52 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)-二叉樹(shù)和二叉查找樹(shù)

摘要：樹(shù)是計(jì)算機(jī)科學(xué)中經(jīng)常用到的一種數(shù)據(jù)結(jié)構(gòu)數(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)以分層的方式存儲(chǔ)數(shù)據(jù)數(shù)被用來(lái)存儲(chǔ)具有層級(jí)關(guān)系的數(shù)據(jù)比如文件系統(tǒng)中的文件樹(shù)還被用來(lái)存儲(chǔ)有序列表本章將研究一種特殊的樹(shù)二叉樹(shù)選擇樹(shù)而不是那些基本的數(shù)據(jù)結(jié)構(gòu)是因?yàn)樵诙鏄?shù)上進(jìn)行查找非常樹(shù)是計(jì)算機(jī)科學(xué)中經(jīng)常用到的一種數(shù)據(jù)結(jié)構(gòu). 數(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu), 以分層的方式存儲(chǔ)數(shù)據(jù). 數(shù)被用來(lái)存儲(chǔ)具有層級(jí)關(guān)系的數(shù)據(jù), 比如文件系統(tǒng)中的文...

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

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

cyrils 2019-08-14 17:52 評(píng)論0 收藏0