一、题目基本信息
级别:【中等】
/**
* 【中序遍历二叉树】给定一个二叉树,返回它的中序 遍历。
*
* 示例:
*
* 输入: [1,null,2,3]
* 1
* \
* 2
* /
* 3
* 输出: [1,3,2]
*
* 递归方式遍历感觉比迭代遍历快
* @Author jiawei huang
* @Since 2019年8月12日
* @Version 1.0
*/
二、解题思路
- 1、最普遍的方式就是递归,二叉树天生就非常适合递归。
- 2、迭代遍历,利用循环,借助栈将迭代的中间结果保存下来,一般迭代需要有一个指向当前位置的类似指针的东西。
三、代码演示
【解法一】
/**
* 1ms,小编自己的解法,递归中序遍历
*
* @param root
* @return
*/
public List<Integer> treeMiddleTraverse(TreeNode root) {
// 如果左子树不为空,那就遍历做子树
if (root.left != null) {
treeMiddleTraverse(root.left);
}
// 2、左子树遍历完后,取中间节点
list.add(root.val);
// 3、如果右子树不为空,那就遍历右子树
if (root.right != null) {
treeMiddleTraverse(root.right);
}
return list;
}
/**
* 1ms递归方式中序遍历
*
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
if (null == root) {
return new ArrayList<>();
}
return treeMiddleTraverse(root);
}
【解法二】
/**
* 2ms迭代方式遍历
*
* @param nums
* @param target
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return list;
}
// 借助栈
Stack<TreeNode> mStack = new Stack<>();
// 1、迭代需要有一个游标
TreeNode currentNode = root;
// 2、迭代的条件
while (currentNode != null || !mStack.isEmpty()) {
// 左子树遍历
while (currentNode != null) {
mStack.push(currentNode);
currentNode = currentNode.left;
}
// 中
currentNode = mStack.pop();
list.add(currentNode.val);
currentNode = currentNode.right;
}
return list;
}
感觉迭代遍历方式比递归耗时一些