題目鏈接

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

題目描述

給定一個(gè)二叉樹，返回它的中序遍歷。
示例:

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

解題方案

思路1：使用遞歸

• 中序遍歷也叫中根遍歷，遍歷時(shí)，根節(jié)點(diǎn)順序在中間，即左跟右。先根遍歷：根左右；后根遍歷：左右根。
• 中根遍歷最重要的一點(diǎn)是：如果當(dāng)前節(jié)點(diǎn)沒有左子樹，記錄其值。
• 成功使用遞歸的關(guān)鍵：保證每一個(gè)節(jié)點(diǎn)的值都會(huì)被記錄，遞歸有兩個(gè)條件：遞歸條件和基線條件。
• 遞歸條件：用于函數(shù)自己調(diào)用自己。這里設(shè)置為如果左/右子樹不為空，遞歸調(diào)用。
• 基線條件：用于保證遞歸會(huì)結(jié)束。這里不用設(shè)置，因?yàn)橹灰獦洳皇菬o窮的，遞歸就能結(jié)束。
• 在計(jì)算機(jī)內(nèi)部，使用調(diào)用棧（Call Stack）來存放函數(shù)。調(diào)用另一個(gè)函數(shù)時(shí)，當(dāng)前函數(shù)暫停并處于為完成狀態(tài)，該函數(shù)的所有變量的值都還在內(nèi)存中。
• 時(shí)間復(fù)雜度：O(n)。

代碼

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        traversal(root, list);
        return list;
    }

    private void traversal(TreeNode root, List<Integer> list) {
        if (root != null) {
            if (root.left != null) {
                traversal(root.left, list);
            }
            list.add(root.val);//如果當(dāng)前節(jié)點(diǎn)沒有左子樹，記錄其值
            if (root.right != null) {
                traversal(root.right, list);
            }
        }
    }
}

畫解

0.png

1.png

2.png

3.png

3-2.png

4.png

5.png

5-2.png

6.png

6-2.png

7.png

8.png

9.png

9-2.png

10.png

10-2.png

image.png

11-2.png

思路2：使用棧

• 使用遞歸時(shí)，如果沒有結(jié)合到函數(shù)調(diào)用棧理解的話，不太好理解
• 在計(jì)算機(jī)內(nèi)部，使用調(diào)用棧來存放函數(shù)，所以可以直接使用棧來實(shí)現(xiàn)，更形象
• 具體參考LeetCode官方題解方法二