LeetCode 94.二叉树的中序遍历

这篇具有很好参考价值的文章主要介绍了LeetCode 94.二叉树的中序遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内

-100 <= Node.val <= 100
给定一个二叉树的根节点 root ，返回 它的中序遍历 。

示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内

-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

方法一递归

思路：

很基础的，中序遍历指的是根节点在中间。左—根—右的顺序。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<Integer>();
        zhongxu(root,res);
        return res;
    }
    public void zhongxu(TreeNode root,List<Integer> res){
        if(root ==null) return ;
        zhongxu(root.left,res);
        res.add(root.val);
        zhongxu(root.right,res);
    }
}

方法二迭代

思路：

第一次学到这个迭代的思想，其实就是用了应该栈来模拟递归，又或者说递归其实隐式地用了一个栈。

先把左节点一个一个全部压入栈，直到没有左节点了。然后弹出栈顶（最左的节点），处理完了，把它的右节点压入栈。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<Integer>();
        Deque<TreeNode> stk=new LinkedList<TreeNode>();
        while(root!=null||!stk.isEmpty()){
            while(root!=null){
                stk.push(root);
                root=root.left;
            }
            root=stk.pop();
            res.add(root.val);
            root=root.right;
        }
        return res;
    }
}

学到Java的栈，一般不用Stack，用Deque。因为Stack慢吧。

Deque可以当队列用，也可以当栈用。

队列：offer() poll() peek()

栈：push() poll()/pop() peek()

参考链接：94. 二叉树的中序遍历 - 力扣（LeetCode）文章来源地址https://www.toymoban.com/news/detail-861421.html

到了这里，关于LeetCode 94.二叉树的中序遍历的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！