Leetcode-094-二叉树的中序遍历

Leecode-094- Binary Tree Inorder Traversal

思路：递归/迭代

题目描述

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

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Java

Solution :递归

递归遍历太简单了

• 前序遍历:打印-左-右
• 中序遍历:左-打印-右
• 后序遍历:左-右-打印

class Solution{
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        helper(root,res);
        return res;
    }

    private void helper(TreeNode root, List<Integer> res) {
        // 判断当前是否是null
        if (root != null){
            // 1. 左子树
            if (root.left != null){
                helper(root.left,res);
            }
            // 2. 打印
            res.add(root.val);
            // 3. 右子树
            if (root.right != null){
                helper(root.right,res);
            }
        }
    }
}

复杂度分析

• 时间复杂度：O（n）
• 空间复杂度：O(h) h是树的高度

Solution :迭代

• 递归实现时，是函数自己调用自己，一层层的嵌套下去
• 操作系统/虚拟机自动帮我们用栈来保存了每个调用的函数，现在我们需要自己模拟这样的调用过程。

递归的调用过程是这样的：

• 递归的调用过程就是不断往左边走，左边走不下去了，就打印节点，再去走右边，然后右边继续这个过程

dfs(root.left)
	dfs(root.left)
		dfs(root.left)
			为null返回
		打印节点
		dfs(root.right)
			dfs(root.left)
				dfs(root.left)
				........

我们在迭代实现时，就可以用栈来模拟上面的调用过程。

// 使用栈模拟递归（迭代）
class Solution{
    public List< Integer > inorderTraversal(TreeNode root) {
        List<Integer>   res   = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()){
            // 一直往左走
            while (curr != null){
                stack.push(curr);
                curr = curr.left;
            }
            // 左边走不下去
            curr = stack.pop();
            // 打印节点的值
            res.add(curr.val);
            // 向右边走
            curr = curr.right;
        }
        return res;
    }
}

• 时间复杂度:O(n)
• 空间复杂度:O(h)，h是树的高度

打赏