題目描述

給定一個二叉樹，返回它的中序 遍歷。

示例:

輸入: [1,null,2,3]
   1
    \
     2
    /
   3

輸出: [1,3,2]

解答方法

方法一：遞歸

代碼

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root:
            return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
        else:
            return[]

時間復(fù)雜度

T(n)=2T(n/2)+1

空間復(fù)雜度

最壞情況下需要空間O(n),平均情況為O(logn)

提交結(jié)果

Runtime: 36 ms, faster than 71.47% of Python3 online submissions for Binary Tree Inorder Traversal.
Memory Usage: 13.7 MB, less than 6.56% of Python3 online submissions for Binary Tree Inorder Traversal.

方法二：基于棧的遍歷

代碼

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        p = root
        while p or stack:
            while p:
                stack.append(p)
                p = p.left
            p = stack.pop()
            res.append(p.val)
            p = p.right
        return res

時間復(fù)雜度

O(n)

空間復(fù)雜度

O(n)

提交結(jié)果

Runtime: 40 ms, faster than 37.12% of Python3 online submissions for Binary Tree Inorder Traversal.
Memory Usage: 13.9 MB, less than 6.56% of Python3 online submissions for Binary Tree Inorder Traversal.

方法三：莫里斯遍歷

代碼

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        current = root
        while current is not None:
            if current.left is None:
                res.append(current.val)
                current = current.right
            else:
                pre = current.left
                while pre.right is not None:
                    pre = pre.right
                pre.right,current.left, current = current, None,  current.left
                
        return res

時間復(fù)雜度

O （n ）。想要證明時間復(fù)雜度是O （n ），最大的問題是找到每個節(jié)點的前驅(qū)節(jié)點的時間復(fù)雜度。乍一想，找到每個節(jié)點的前驅(qū)節(jié)點的時間復(fù)雜度應(yīng)該是O （nlogn ），因為找到一個節(jié)點的前驅(qū)節(jié)點和樹的高度有關(guān)。
但事實上，找到所有節(jié)點的前驅(qū)節(jié)點只需要O （n ）時間。一棵?個節(jié)點的二叉樹只有?- 1條邊，每條邊只可能使用2次，一次是定位節(jié)點，一次是找前驅(qū)節(jié)點。
故復(fù)雜度為O （n ）。

空間復(fù)雜度

O （n ）。使用了長度為?的數(shù)組。

提交結(jié)果

Runtime: 40 ms, faster than 37.12% of Python3 online submissions for Binary Tree Inorder Traversal.
Memory Usage: 13.9 MB, less than 6.56% of Python3 online submissions for Binary Tree Inorder Traversal.