67.二叉树的中序遍历(高频)

描述

给出一棵二叉树,返回其中序遍历

样例

给出二叉树 {1,#,2,3},

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

挑战

你能使用非递归算法来实现么?

中序

左根右

代码

/**
 * 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;
            }
            // 此时当前结点的左儿子已经为空
            curt = stack.pop();
            result.add(curt.val);
            /* 当前结点的右儿子如果为空，证明当前结点是叶子结点则会进入下一轮while循环，
             * 当栈不为空时会 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