要成功就做一百题-98

题目名称

二叉树的中序遍历

描述

给定一个先序遍历的二叉树，打印出其中序（中根）遍历的结构。

示例:

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

输出: [1,3,2]

解题思路

首先是根据定义的结构，构造对应的二叉树，然后根据中根遍历的方式，先定义个数组，保存结果数值，在一次用先左，再中，后右的形式，遍历二叉树节点，存入结果就可以了。这里先不考虑非递归的实现。如下是代码。

代码

   @Test
    public void bTree(){
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        root.left = new TreeNode(2);
        System.out.println(inorderTraversal(root));
    }

    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        traversal(root);
        return list;
    }

    private void traversal(TreeNode node){
        if(null == node){
            return;
        }
        TreeNode left = node.left;
        TreeNode right = node.right;
        if(null != left){
            traversal(left);
        }
        list.add(node.val);
        if(null != right){
            traversal(right);
        }
    }

总结

二叉树相关很多使用了递归的方式，递归看起来也好理解。非递归遍历，相比较而言更有挑战性，目前想到的使用队列、栈结构实现，后面再做补充。