讨论/《零起步学算法》 - 例题:二叉树的后序遍历/
《零起步学算法》 - 例题:二叉树的后序遍历
共 3 个回复

这样也行,把前序遍历的:根左右变为根右左,然后倒叙输出就成了左右根

    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<Integer> stack = new LinkedList();
        List<Integer> res = new ArrayList();
        if(root == null) return res;
        Deque<TreeNode> dq = new LinkedList();
        dq.addLast(root);
        while(!dq.isEmpty()){
            TreeNode node = dq.pollLast();
            stack.addFirst(node.val);
            if(node.left != null){
                dq.addLast(node.left);
            }
            if(node.right != null){
                dq.addLast(node.right);
            }
        }
        while(!stack.isEmpty()){
            res.add(stack.poll());
        }
        return res;
    }
1

解释一下:
root.right == preNode
说白了就是记录上一个节点的信息

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
      List<Integer> res= new LinkedList<>();
      if(null == root) {
        return res;
      }
      //栈
      Deque<TreeNode> stack = new LinkedList<>();
      //记录上一个节点
      TreeNode preNode = null;
      while(root != null || !stack.isEmpty()) {
        if(root != null) {
          stack.addLast(root);
          root = root.left;
        } else {
          root = stack.removeLast();
          if(root.right == null || root.right == preNode) {
            res.add(root.val);
            preNode = root;
            root = null;
          } else {
            stack.addLast(root);
            root = root.right;
          }
        }
      }
      return res;
    }
}
1

厉害厉害