成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode 94. Binary Tree Inorder Traversal

wpw / 1033人閱讀

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

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

遞歸

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

    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é)點存在左子節(jié)點，則繼續(xù)遍歷左子樹直到最后一個左子節(jié)點。然后依次處理棧中的元素。如果棧頂元素有右子節(jié)點，則將其右子節(jié)點壓入棧中作為root，再繼續(xù)遍歷root的左子節(jié)點。當(dāng)root和stack都為空時，遍歷結(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;
    }


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

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67420.html

相關(guān)文章

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

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

    henry14 評論0 收藏0

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

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

    Jason 評論0 收藏0

  • 94. Binary Tree Inorder Traversal

    摘要：題目解答合并兩個直接就好啦的方法很巧妙，當(dāng)時想了很久也沒做出來，所以這里標(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 評論0 收藏0

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

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

    caoym 評論0 收藏0

  • [LintCode/LeetCode] Binary Tree InOrder Traversal

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

    tomorrowwu 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<