成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

leetcode 94. Binary Tree Inorder Traversal

wpw / 1080人閱讀

摘要：題目要求中序遍歷樹(shù)，并將遍歷結(jié)果添加到數(shù)組中。分別用遞歸和循環(huán)的方式結(jié)局。如果當(dāng)前節(jié)點(diǎn)存在左子節(jié)點(diǎn)，則繼續(xù)遍歷左子樹(shù)直到最后一個(gè)左子節(jié)點(diǎn)。如果棧頂元素有右子節(jié)點(diǎn)，則將其右子節(jié)點(diǎn)壓入棧中作為，再繼續(xù)遍歷的左子節(jié)點(diǎn)。當(dāng)和都為空時(shí)，遍歷結(jié)束。

題目要求 
Given a binary tree, return the inorder traversal of its nodes" values.

For example:
Given binary tree [1,null,2,3],
   1
    
     2
    /
   3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

中序遍歷樹(shù)，并將遍歷結(jié)果添加到數(shù)組中。分別用遞歸和循環(huán)的方式結(jié)局。

遞歸

核心的思路就是先遞歸左側(cè)子節(jié)點(diǎn)，之后讀取中間節(jié)點(diǎn)的值，再遞歸右側(cè)子節(jié)點(diǎn)。

    public List inorderTraversal(TreeNode root) {
        List result = new ArrayList();
        inorderTraversal(root, result);
        return result;
    }
    
    public void inorderTraversal(TreeNode root, List result){
        if(root==null) return;
        inorderTraversal(root.left, result);
        result.add(root.val);
        inorderTraversal(root.right, result);
    }
循環(huán)

這里需要利用棧的數(shù)據(jù)結(jié)構(gòu)。如果當(dāng)前節(jié)點(diǎn)存在左子節(jié)點(diǎn)，則繼續(xù)遍歷左子樹(shù)直到最后一個(gè)左子節(jié)點(diǎn)。然后依次處理?xiàng)Ｖ械脑?。如果棧頂元素有右子?jié)點(diǎn)，則將其右子節(jié)點(diǎn)壓入棧中作為root，再繼續(xù)遍歷root的左子節(jié)點(diǎn)。當(dāng)root和stack都為空時(shí)，遍歷結(jié)束。

    public List inorderTraversal2(TreeNode root) {
        List result = new ArrayList();
        if(root==null) return result;
        
        LinkedList stack = new LinkedList();
        do{
            while(root!=null){
                stack.push(root);
                root = root.left; 
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }while(!(stack.isEmpty() && root==null));
        return result;
    }


想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

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

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

相關(guān)文章

  • leetcode講解--94. Binary Tree Inorder Traversal

    摘要：題目地址嗯，經(jīng)典的題目，中序遍歷二叉樹(shù)。代碼如下中序遍歷先序遍歷后序遍歷是不是簡(jiǎn)單的不要不要的，遞歸就是這么美。右孩子后壓棧全部釋放出來(lái)嗯，總的來(lái)說(shuō)用迭代遍歷確實(shí)燒腦，沒(méi)什么性能上的特殊需求還是用遞歸寫法吧，對(duì)程序員友好哦。 94. Binary Tree Inorder Traversal Given a binary tree, return the inorder travers...

    henry14 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第94題 —— 二叉樹(shù)的中序遍歷

    摘要：小鹿題目二叉樹(shù)中序遍歷給定一個(gè)二叉樹(shù)，返回它的中序遍歷。通常遞歸的方法解決二叉樹(shù)的遍歷最方便不過(guò)，但是我還是喜歡增加點(diǎn)難度，用一般的迭代循環(huán)來(lái)實(shí)現(xiàn)。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿 題目：Binary Tree Inorder Traversal（二叉樹(shù)中序遍歷...

    Jason 評(píng)論0 收藏0

  • 94. Binary Tree Inorder Traversal

    摘要：題目解答合并兩個(gè)直接就好啦的方法很巧妙，當(dāng)時(shí)想了很久也沒(méi)做出來(lái)，所以這里標(biāo)注一下 題目：Given a binary tree, return the inorder traversal of its nodes values. For example:Given binary tree [1,null,2,3], 1 2 / 3 return ...

    dackel 評(píng)論0 收藏0

  • [Leetcode] Construct Binary Tree from Traversal 根據(jù)

    摘要：二分法復(fù)雜度時(shí)間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點(diǎn)。對(duì)于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹(shù)，后半部分是根的右子樹(shù)。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...

    caoym 評(píng)論0 收藏0

  • [LintCode/LeetCode] Binary Tree InOrder Traversal

    摘要：遞歸法不說(shuō)了，棧迭代的函數(shù)是利用的原理，從根節(jié)點(diǎn)到最底層的左子樹(shù)，依次入堆棧。然后將出的結(jié)點(diǎn)值存入數(shù)組，并對(duì)出的結(jié)點(diǎn)的右子樹(shù)用函數(shù)繼續(xù)迭代。 Problem Given a binary tree, return the inorder traversal of its nodes values. Example Given binary tree {1,#,2,3}, 1 ...

    tomorrowwu 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<