1. 代码段小站首页
  2. 算法

leetcode145-二叉树的后序遍历

彭晨涛 • • 算法 • 阅读 7

原题

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

示例:

输入: [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)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年1月10日 15:37
下一篇 2020年1月10日 22:55

相关推荐

发表回复

登录后才能评论