题解 | #二叉树中序遍历#
二叉树的中序遍历
http://www.nowcoder.com/practice/0bf071c135e64ee2a027783b80bf781d
// NC161 二叉树的中序遍历
思想以及分析：
中序遍历 返回的是 左子树、根、右子树对应的值( ".val"获取)
使用递归先从左子树开始，当该循环中止(这里的意思是说最里层的那层循环中止了，因为这时递归到左子树最末端,这时的节点没有左子树了) ，将值赋到 arrList中。再去递归右子树(这样会从最末端的右子树开始)
如果使用非递归解决问题，可以考虑栈stack进行节点的存取，这和栈的先进后出的性质有关，由上面的解析可知，遍历到左子树的最尾端后，再将节点弹出并将节点值（节点内容）添加到arrList中。再去查找右子树进行循环（和递归的方法异曲同工）
这里有一个问题，就是返回值是int，但如果使用了ArrayList，则泛型中的Integer 是int的封装类，要么 新建一个 int数组，且该数组的长度根据动态数组ArrayList的长度而定，通过for循环 将Integer型的列表ArrayList中的值 转给 int型数组，从而返回正确类型。 或者 使用 stream().mapToInt(Integer::valueOf).toArray() 将Integer型转换成 int （这里涉及到了 流 的内容）
代码实现：非递归采取栈
public int[] inorderTraversal (TreeNode root) {
ArrayList<Integer> arrList=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
while(root!=null || !stack.isEmpty()){
while(root!=null){
stack.push(root);
root=root.left;
}
root=stack.pop();
arrList.add(root.val);
root=root.right;
}
return arrList.stream().mapToInt(Integer::valueOf).toArray();
} 代码实现：递归
public int[] inorderTraversal (TreeNode root) {
ArrayListarrList=new ArrayList<>();
inorderTraver(root,arrList);
//如果使用 for循环来遍历得到int数组，则 需要 return arr;
//int[] arr=new int[arrList.size()];
//for(int i=0;i<arr.length>
</arr.length>
<arr.length>
</arr.length>
投递美团等公司10个岗位
查看9道真题和解析