leetcode 94. Binary Tree Inorder Traversal

wpw 發布于2019-08-15 10:54 / 1023人閱讀

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

題目要求

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?

中序遍歷樹，并將遍歷結果添加到數組中。分別用遞歸和循環的方式結局。

遞歸

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

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

循環

這里需要利用棧的數據結構。如果當前節點存在左子節點，則繼續遍歷左子樹直到最后一個左子節點。然后依次處理棧中的元素。如果棧頂元素有右子節點，則將其右子節點壓入棧中作為root，再繼續遍歷root的左子節點。當root和stack都為空時，遍歷結束。

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

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 binary-tree binary-search-tree Inorder Traversal

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67420.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 之 JavaScript 解答第94題 —— 二叉樹的中序遍歷

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

Jason 2019-08-23 17:19 評論0 收藏0
94. Binary Tree Inorder Traversal

摘要：題目解答合并兩個直接就好啦的方法很巧妙，當時想了很久也沒做出來，所以這里標注一下題目：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 2019-08-14 14:12 評論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
[LintCode/LeetCode] Binary Tree InOrder Traversal

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

tomorrowwu 2019-08-14 15:39 評論0 收藏0