94. Binary Tree Inorder Traversal

dackel 發布于2019-08-14 14:12 / 2426人閱讀

摘要：題目解答合并兩個直接就好啦的方法很巧妙，當時想了很久也沒做出來，所以這里標注一下

題目：
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;
    }
    
    //合并兩個list,直接addAll就好啦
    result.addAll(inorderTraversal(root.left));
    result.add(root.val);
    result.addAll(inorderTraversal(root.right));
    
    return result;
}

Iteratively

//Iterative的方法很巧妙，當時想了很久也沒做出來，所以這里標注一下
    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云服務器云服務器 binary-tree binary-search-tree Inorder Traversal

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64872.html

leetcode講解--94. Binary Tree Inorder Traversal

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

henry14 2019-07-25 11:22 評論0 收藏0
leetcode 94. Binary Tree Inorder Traversal

摘要：題目要求中序遍歷樹，并將遍歷結果添加到數組中。分別用遞歸和循環的方式結局。如果當前節點存在左子節點，則繼續遍歷左子樹直到最后一個左子節點。如果棧頂元素有右子節點，則將其右子節點壓入棧中作為，再繼續遍歷的左子節點。當和都為空時，遍歷結束。題目要求 Given a binary tree, return the inorder traversal of its nodes values....

wpw 2019-08-15 10:54 評論0 收藏0
LeetCode 之 JavaScript 解答第94題 —— 二叉樹的中序遍歷

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

Jason 2019-08-23 17:19 評論0 收藏0
二叉樹遍歷算法收集(先序 preorder，后序 postorder，中序 inorder）循環+

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

沈建明 2019-08-14 15:55 評論0 收藏0
[Leetcode] Construct Binary Tree from Traversal 根據

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

caoym 2019-08-14 12:32 評論0 收藏0