leetcode94-二叉树的中序遍历

原题

给定一个二叉树,返回它的 中序 遍历。

示例:

输入: [1,null,2,3]  1
  \
   2
  /
 3
输出: [1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解法

思想

DFS,递归方法着实很简单,迭代很抽象。

代码

递归:

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

迭代,我一开始这么写的,用一个HashSet记录栈存储过的节点:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> ans = new ArrayList<>();
        Set<TreeNode> set = new HashSet<>();
        stack.push(root);
        if(root == null) return ans;
        while(!stack.empty()){
            TreeNode node = stack.peek();
            if(null!=node.left && !set.contains(node.left)) {
                stack.push(node.left);
                set.add(node.left);
            }
            else{
                ans.add(node.val);
                stack.pop();
                if(null!=node.right) 
                    stack.push(node.right);
                node = null;
            }
        }
        return ans;
    }
}

然后看到官方的写法,这才是递归转化过来的写法:

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

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode94-%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e4%b8%ad%e5%ba%8f%e9%81%8d%e5%8e%86/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月11日
下一篇 2019年12月13日

相关推荐

  • leetcode100-相同的树

    原题 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 …

    算法 2020年5月7日
    0210
  • leetcode32-最长有效括号

    原题 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2…

    算法 2020年6月12日
    0160
  • leetcode62-不同路径

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月21日
    0360
  • leetcode274-H指数

    原题 https://leetcode.cn/problems/h-index/description 题解 核心是求数组中,大于等于h的数的个数 大于等于 h,个数的最大值。 核…

    算法 2024年3月18日
    050
  • leetcode1160-拼写单词

    原题 给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。 假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字…

    算法 2020年3月17日
    0130
  • leetcode162-寻找峰值

    原题 峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。 数组可能包含多个峰值,在这种情况…

    算法 2020年1月3日
    060
  • leetcode232-用栈实现队列

    原题 使用栈实现队列的下列操作: push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – …

    算法 2019年12月13日
    0560
  • leetcode295-数据流的中位数

    原题 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.…

    算法 2020年2月12日
    0100
  • leetcode119-杨辉三角II

    原题 给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 3 输出: [1,3,3,1] 进阶: …

    2019年11月22日
    0280
  • leetcode39-组合总和

    原题 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates …

    2020年5月1日
    02730

发表回复

登录后才能评论