【中序遍历二叉树】----LeetCode算法题(二)

331 阅读1分钟

一、题目基本信息

题目传送门--中序遍历二叉树

级别:【中等】
/**
 * 【中序遍历二叉树】给定一个二叉树,返回它的中序 遍历。
 * 
 * 示例:
 * 
 * 输入: [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;
}

感觉迭代遍历方式比递归耗时一些