二叉树的中序遍历

94 二叉树的中序遍历

题目描述

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

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

输出: [1,3,2]

解法1 递归法

使用经典的递归法实现，编写一个辅助函数实现递归。

实现代码

/**
 * 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> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        helper(root, list);
        return list;
    }

    public void helper(TreeNode root, List<Integer> res) {
        if (root.left != null) {
            helper(root.left, res);
        }
        res.add(root.val);
        if (root.right != null) {
            helper(root.right, res);
        }
    }
}

复杂度分析

时间复杂度	O(n)
空间复杂度	最坏情况下需要空间O(n)，平均情况为O(logn)

解法2 迭代法

基于栈的遍历

代码实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            while ( root != null || !stack.empty()) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
            return res;
        }
}

复杂度分析

时间复杂度	O(n)
空间复杂度	O(n)

解法3 颜色标记法

使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。

代码实现

class Solution {
    public class ColorNode {
        TreeNode root;
        String color;

       public ColorNode(TreeNode root, String color) {
            this.root = root;
            this.color = color;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        if (root == null) return null;
        stack.push(new ColorNode(root, "white"));
        while (!stack.isEmpty() ) {
            ColorNode colorNode = stack.pop();
            if (colorNode.color.equals("white")) {
                if (colorNode.root.right != null) {
                    stack.push(new ColorNode(colorNode.root.right, "white"));
                }
                stack.push(new ColorNode(colorNode.root, "gray"));
                if (colorNode.root.left != null) {
                    stack.push(new ColorNode(colorNode.root.left, "white"));
                }
            } else {
                res.add(colorNode.root.val);
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度	O(n)
空间复杂度	O(n)

在IntelliJ IDEA中测试

package com.cn.algorithm;

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

/**
 * @Author: cyh
 * @Description: 二叉树的中序遍历
 * 三种方法：1、递归法 2、迭代法 3、颜色标记法
 **/
public class inorderTraversalDemo {

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

    /**
     * 1.递归法
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public void helper(TreeNode root, List<Integer> res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
            }
        }
    }

    /**
     * 2.非递归版
     * 用栈实现，迭代法
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while ( root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

    /**
     * 3.颜色标记法
     */
    public class ColorNode {
        TreeNode root;
        String color;

       public ColorNode(TreeNode root, String color) {
            this.root = root;
            this.color = color;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        if (root == null) return null;
        stack.push(new ColorNode(root, "white"));
        while (!stack.isEmpty() ) {
            ColorNode colorNode = stack.pop();
            if (colorNode.color.equals("white")) {
                if (colorNode.root.right != null) {
                    stack.push(new ColorNode(colorNode.root.right, "white"));
                }
                stack.push(new ColorNode(colorNode.root, "gray"));
                if (colorNode.root.left != null) {
                    stack.push(new ColorNode(colorNode.root.left, "white"));
                }
            } else {
                res.add(colorNode.root.val);
            }
        }
        return res;
    }


    /**
     * 将数组转化为树结构
     * @param array
     * @param index
     * @return
     */
    TreeNode arrayToTree(Integer[] array, int index) {
        TreeNode root = null;
        if (index < array.length) {
            Integer value = array[index];
            if (value == null) {
                return null;
            }
            root = new TreeNode(value);
            root.left = arrayToTree(array, 2*index + 1);
            root.right = arrayToTree(array, 2*index + 2);
            return root;
        }
        return root;
    }

    public static void main(String[] args) {
        Integer[] arr = {1,null,2,null,null,3};
        inorderTraversalDemo it = new inorderTraversalDemo();
        TreeNode root = it.arrayToTree(arr, 0);
        List<Integer> list = it.inorderTraversal(root);
        System.out.println(list);
    }
}

输出结果：

[1, 3, 2]