描述

給出一棵二叉樹,返回其中序遍歷

樣例

給出二叉樹 {1,#,2,3},

   1
    \
     2
    /
   3
返回 [1,3,2].

挑戰(zhàn)

你能使用非遞歸算法來實現(xiàn)么?

中序

左根右

代碼

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

1. 非遞歸(重點)

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        TreeNode curt = root;
        // curt == null 但 stack 為非空 說明當前結點為二叉樹葉子結點，但中序遍歷還未結束
        while (curt != null || !stack.empty()) {
            while (curt != null) {
                // 一直找，找到最左邊結點，即中序遍歷輸出的第一個結點
                stack.push(curt);
                curt = curt.left;
            }
            // 此時當前結點的左兒子已經(jīng)為空
            curt = stack.pop();
            result.add(curt.val);
            /* 當前結點的右兒子如果為空，證明當前結點是葉子結點則會進入下一輪while循環(huán)，
             * 當棧不為空時會 pop 出當前結點的根結點，curt 指向新的結點
             */
            curt = curt.right;
        }
        return result;
    }
}

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

2. 遍歷+遞歸

public class Solution {
    /*
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> results = new ArrayList<>();
        traversal(root, results);
        return results;
    }
    
    private void traversal(TreeNode root, List<Integer> results) {
        if (root == null) {
            return;
        }
        
        traversal(root.left, results);
        results.add(root.val);
        traversal(root.right, results);
    }
}

3. 分治+遞歸

public class Solution {
    /*
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> results = new ArrayList<>();
        
        if (root == null) {
            return results;
        }
        
        List<Integer> left = inorderTraversal(root.left);
        List<Integer> right = inorderTraversal(root.right);
        
        results.addAll(left);
        results.add(root.val);
        results.addAll(right);
        
        return results;
    }
}

http://blog.csdn.net/u012877472/article/details/49401751