LeetCode中二叉樹周遊問題

前置知識

二叉樹周遊的相關知識, 可以參考我的另外一篇二分搜尋樹的博文,位址如下:

https://blog.csdn.net/love905661433/article/details/82981527

前序周遊

LeetCode-144. 二叉樹的前序周遊

題目

給定一個二叉樹，傳回它的 前序 周遊。

示例:

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

輸出: [1,2,3]
           

進階: 遞歸算法很簡單，你可以通過疊代算法完成嗎？

解題

class Solution {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderTraversal(root, result);
        return result;
    }

    private void preorderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        result.add(root.val);
        preorderTraversal(root.left, result);
        preorderTraversal(root.right, result);
    }
}
           

中序周遊

LeetCode-94. 二叉樹的中序周遊

題目

給定一個二叉樹，傳回它的中序 周遊。

示例:

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

輸出: [1,3,2]

進階: 遞歸算法很簡單，你可以通過疊代算法完成嗎？

解題

class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderTraversal(root, result);
        return result;
    }

    private void inorderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left, result);
        result.add(root.val);
        inorderTraversal(root.right, result);
    }
}
           

後序周遊

LeetCode-145. 二叉樹的後序周遊

題目

給定一個二叉樹，傳回它的 後序 周遊。

示例:

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

輸出: [3,2,1]
           

進階: 遞歸算法很簡單，你可以通過疊代算法完成嗎？

解題

class Solution {

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderTraversal(root, result);
        return result;
    }

    private void postorderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        postorderTraversal(root.left, result);
        postorderTraversal(root.right, result);
        result.add(root.val);
    }
}
           

總結

使用遞歸方法解決二叉樹的周遊是非常簡單的, 如果使用非遞歸的方式的話, 就稍微複雜一點, 可以使用棧來輔助, 其實遞歸其實也是使用了棧的, 不過是系統棧而已, 是以可以顯式的使用棧來模拟系統棧