144. 二叉樹的先序周遊

1. 題目描述

題目連結

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

示例:

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

1

\

2

/

3

輸出: [1,2,3]

2. 題目分析

先序周遊二叉樹順序是，先周遊根節點，然後周遊左孩子，最後周遊右孩子，周遊有兩種實作方式，一種是遞歸實作，一種是非遞歸實作。

• 遞歸實作：簡單、易了解，但吃記憶體，了解jvm的記憶體配置設定模型的同學一定知道，遞歸方法，每一次遞歸，都需要在虛拟機棧中儲存目前方法的出口、入口、局部變量等，這些會占用大量的記憶體，然後就容易出現oom問題（記憶體洩漏），是以一般開發環境會禁止使用比較深的遞歸。進而采用動态規劃那種備忘錄形式的非遞歸實作。
• 非遞歸實作：非遞歸實作，需要解決備忘錄的資料結構，根據周遊節點時的先進後出的順序特點，是以采用棧結構暫時存儲已經得到的節點。

3. 解決思路

• 遞歸實作：遞歸很好了解的原因是，遞歸隻需要關注兩個點，一是遞歸結束标志，而是目前節點的周遊方式；把每一個目前節點都看作是根節點，那麼擷取到目前節點的值，然後周遊周遊左孩子，最後周遊右孩子，這樣就實作了整顆二叉樹的周遊。
• 非遞歸實作：使用棧存儲已經得到的節點。

4. 代碼實作（java）

• 遞歸實作

/**
     * 先序周遊:遞歸實作
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal_1(TreeNode root) {
        List<Integer> result= new ArrayList<>();
        if (root == null){
            return result;
        }
        return preorderTraversalWithRecursion(root,result);
    }

    /**
     * 先序周遊的遞歸實作方法
     * @param root
     * @param result
     * @return
     */
    public List<Integer> preorderTraversalWithRecursion(TreeNode root,List<Integer> result) {
        if (root == null){
            return result;
        }
        result.add(root.val);
        preorderTraversalWithRecursion(root.left,result);
        preorderTraversalWithRecursion(root.right,result);
        return result;
    }
           

• 非遞歸實作

package com.algorithm.leetcode.binarytree;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

/**
 * Created by 淩 on 2018/12/9.
 */
public class BTree {
    //表示空節點
    public static final int FLAG = -1;

    public static void main(String[] args) {
        BTree bTree = new BTree();
        TreeNode root = null;
        System.out.println("按先序周遊，輸入所有節點值：");
        root = bTree.buildBTree(root);
//        List<Integer> result = bTree.inorderTraversal(root);
//        List<Integer> result = bTree.preorderTraversal(root);
        List<Integer> result = bTree.postorderTraversal(root);
        for(Integer val: result){
            System.out.printf(val + "\t");
        }
        System.out.println("");
    }
    /**
     * 先序周遊建構二叉樹:1 2 -1 4 -1 -1 3 5 -1 -1 -1
     *       1
     *      / \
     *     2   3
     *     \   /
     *     4  5
     * @param treeNode
     * @return
     */
    public TreeNode buildBTree(TreeNode treeNode){
        //遞歸建樹二叉樹
        Scanner input = new Scanner(System.in);
        int val = input.nextInt();
        //用FLAG區分沒有子結點的情況
        if (val != FLAG) {
            treeNode=new TreeNode(val);
            treeNode.left=buildBTree(treeNode.left);
            treeNode.right=buildBTree(treeNode.right);
        }
        return treeNode;
    }

    /**
     * 先序周遊
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result= new ArrayList<>();
        if (root == null){
            return result;
        }
        TreeNode node = root;
        Stack<TreeNode> stack =new Stack<>();

        while (node != null || !stack.isEmpty()){
            //找到最左葉子節點
            if (node != null){
                result.add(node.val);
                stack.push(node);
                node = node.left;
            }else{
                node = stack.pop();
                node = node.right;
            }
        }
        return result;
    }
}

class TreeNode {
    int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}