BM24 题解 | #二叉树的中序遍历#

学习心得：good job！自己做出来的！

中序遍历的，没有什么好说的，就一个递归方法，visit放中间。

用栈的方法，就很有意思了，这次通过自己写，不断调试，发现如下规律：

1、外层while循环，为什么要写成 (root!=null || stack.isEmpty()){}？

是因为中序遍历的栈是在root==null和stack.pop()之间来回循环的。

2、所有的数据添加中间while的循环里面，不再外面的while或者更外面

是因为需要进入一个循环不断，从根节点，添加左子节点

3、最下面则是当root为空时，进入pop数据，不断取出数据的同时，把root指向pop出来的数据的right节点。

解题思路：

1、递归调用，visit处于中间

2、stack循环，两个循环。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    
    public int[] inorderTraversal (TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();

        Stack<TreeNode> stack = new Stack<>();
        while(root!=null  || !stack.isEmpty()) {
            while(root!=null) {
                stack.push(root);
                root = root.left;
            }

            TreeNode top = stack.pop();
            res.add(top.val);
            root = top.right;
        }

        int[] arr = new int[res.size()];
        for(int i=0; i<arr.length; i++) {
            arr[i] = res.get(i);
        }
        return arr;
    }


    /**
     * 我使用的递归的方法
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] inorderTraversal2 (TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorderTraversal(root, res);
        int[] arr = new int[res.size()];
        for(int i=0; i<arr.length; i++) {
            arr[i] = res.get(i);
        }
        return arr;
    }

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