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

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

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

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);
}

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

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

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

相關(guān)文章

樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時(shí)間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點(diǎn)個(gè)數(shù)。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(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ù)據(jù)類型或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時(shí)間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點(diǎn)個(gè)數(shù)。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(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中的二叉樹遍歷

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

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

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

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

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

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