94. Binary Tree Inorder Traversal

dackel 發(fā)布于2019-08-14 14:12 / 2491人閱讀

摘要：題目解答合并兩個(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],

return [1,3,2].

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

解答：

Recursive:

public List inorderTraversal(TreeNode root) {
    List result = new ArrayList();
    if (root == null) return result;
    if (root.left == null && root.right == null) {
        result.add(root.val);
        return result;
    }
    
    //合并兩個(gè)list,直接addAll就好啦
    result.addAll(inorderTraversal(root.left));
    result.add(root.val);
    result.addAll(inorderTraversal(root.right));
    
    return result;
}

Iteratively

//Iterative的方法很巧妙，當(dāng)時(shí)想了很久也沒(méi)做出來(lái)，所以這里標(biāo)注一下
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList();
        Stack stack = new Stack();
        
        TreeNode curt = root;
        while (curt != null || !stack.isEmpty()) {
            while (curt != null) {
                stack.push(curt);
                curt = curt.left;
            }
            curt = stack.pop();
            list.add(curt.val);
            curt = curt.right;
        }
        return list;
    }

GPU云服務(wù)器云服務(wù)器 binary-tree binary-search-tree Inorder Traversal

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64872.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 2019-07-25 11:22 評(píng)論0 收藏0
leetcode 94. Binary Tree Inorder Traversal

摘要：題目要求中序遍歷樹(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....

wpw 2019-08-15 10:54 評(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 2019-08-23 17:19 評(píng)論0 收藏0
二叉樹(shù)遍歷算法收集(先序 preorder，后序 postorder，中序 inorder）循環(huán)+

摘要：指的是的位置。算法比較簡(jiǎn)單，算法比較難想，可是原題都說(shuō)了 preorder: root-left-rightinorder: left-root-rightpostorder: left-right-root order指的是root的位置。 recursive算法比較簡(jiǎn)單，iterative算法比較難想，可是leetcode原題都說(shuō)了： recursive method is tri...

沈建明 2019-08-14 15:55 評(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 2019-08-14 12:32 評(píng)論0 收藏0