leetcode145-二叉树的后序遍历

原题

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

示例:

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

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

解法

思想

  1. 递归
  2. 迭代(不同于前序遍历和中序遍历,后序遍历迭代更麻烦)
  3. 逆转前序遍历

代码

递归:

/**
 * 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> postorderTraversal(TreeNode root) {
        if(root!=null){         
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            ans.add(root.val);
        }
        return ans;
    }
}

迭代:

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    TreeNode last = null;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            TreeNode temp = stack.peek();
            //是否变到右子树
            if (temp.right != null && temp.right != last) {
                cur = temp.right;
            } else {
                list.add(temp.val);
                last = temp;
                stack.pop();
            }
        }
    }
    return list;
}

逆转前序遍历:(来源leetcode官方)

class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      output.addFirst(node.val);
      if (node.left != null) {
        stack.add(node.left);
      }
      if (node.right != null) {
        stack.add(node.right);
      }
    }
    return output;
  }
}

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

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月10日
下一篇 2020年1月10日

相关推荐

  • 蓝桥杯试题-小数第n位

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。  如果我们把有限小数的末尾加上无限多个…

    算法 2020年2月29日
    080
  • leetcode983-最低票价

    原题 在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车…

    算法 2020年5月6日
    0120
  • leetcode374-猜数字大小

    原题 我们正在玩一个猜数字游戏。 游戏规则如下:我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了,我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接…

    算法 2019年12月31日
    0370
  • leetcode155-最小栈

    原题 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() …

    算法 2019年12月11日
    0130
  • leetcode96-不同的二叉搜索树

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: &…

    算法 2020年1月22日
    0120
  • 用一个栈实现另一个栈的排序

    原题(来源牛客网) 一个栈中元素的类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只许申请一个栈。除此之外,可以申请新的变量,但不能申请额外的数据结构。如何完成排序? 解法 …

    算法 2020年4月20日
    02110
  • leetcode682-棒球比赛

    原题 你现在是棒球比赛记录员。给定一个字符串列表,每个字符串可以是以下四种类型之一:1. 整数(一轮的得分):直接表示您在本轮中获得的积分数。2. "+"(一轮的得…

    算法 2020年2月3日
    0210
  • leetcode142-环形链表II

    原题 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始…

    2019年12月14日
    0440
  • leetcode876-链表的中间结点

    原题 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入: [1,2,3,4,5] 输出: 此列表中的结…

    算法 2020年3月23日
    090
  • 剑指offer51-数组中的逆序对

    原题(来源Leetcode) 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7…

    算法 2020年4月24日
    0400

发表回复

登录后才能评论