算法日记-LeetCode-94.二叉树的中序遍历

2023-07-16

字数统计: 192字 | 阅读时长≈ 1分

算法日记-LeetCode-94.二叉树的中序遍历

原题链接：94. 二叉树的中序遍历 - 力扣（LeetCode）

题目

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

解题思路

迭代
递归

代码

迭代

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while(!stack.empty() || node != null){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            list.add(node.val);
            node = node.right;
        }
        return list;
    }
}

递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        traversal(root, list);
        return list;
    }
    public void traversal(TreeNode root, List<Integer> list){
        if(root==null) return;
        traversal(root.left, list);
        list.add(root.val);
        traversal(root.right, list);
    }
}

本文作者： Naskete
本文链接： https://Naskete.github.io/2023/07/16/algorithm/算法日记-LeetCode-94.二叉树的中序遍历/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！