题目描述

给定一个二叉树，返回它的中序 遍历。

样例

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

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

算法1

若当前节点不为空，则递归把左子树所有结点的值放进ans中，再将当前节点的值放进ans中，再递归把右子树所有结点的值放进ans中

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    static List<Integer> ans = new ArrayList<Integer>();
    static void dfs(TreeNode root)
    {
        if(root != null)
        {
            dfs(root.left);
            ans.add(root.val);
            dfs(root.right);
        }
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        ans.clear();
        dfs(root);
        return ans;
    }
}

算法2

迭代

将整课树的最左边一条链压入栈中，每次取出栈顶元素，并记录栈顶元素，如果它有右子树，则将右子树压入栈中。

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode p = root;
        while(p != null || !stk.isEmpty())//说明还有元素能放进栈中 和 栈中有元素未访问
        {
            while(p != null)
            {
                stk.add(p);
                p = p.left;
            }
            p = stk.pop();
            ans.add(p.val);
            p = p.right;
        }

        return ans;
    }
}