144. Pre-sequence traversal of the binary tree

Given a binary tree, return its previous traversal.

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,2,3]
Advanced: The recursive algorithm is very simple, can you do it through an iterative algorithm?

Source: LeetCode
Link: https://leetcode-cn.com/problems/binary-tree-preorder-traversal
Copyright The collar is owned by the network. For commercial reprints, please contact the official authorization. For non-commercial reprints, please indicate the source.

 1 class< span style="color: #000000;"> Solution {

 2 public List preorderTraversal(TreeNode root) {

 3 if (root == null) return new ArrayList< >();

 4 // The non-recursive algorithm of pre-order traversal and the non-recursive algorithm of post-order traversal

 5 Stack pre = new Stack<>();

 6

 7 List res = new ArrayList<>();

 8

 9 TreeNode p = root;

10 do {

11 for (TreeNode i = p; i! = null; i = i.left) {

12  res.add(i.val);

13  pre.push(i);

14 }

15 p = pre.pop().right;

16} while (p != null || !pre.empty());

17 return res;

18 }

19 }

 1 class Solution {

 2 public List preorderTraversal(TreeNode root) {

 3 if (root == null) return new ArrayList< >();

 4 // The non-recursive algorithm of pre-order traversal and the non-recursive algorithm of post-order traversal

 5 Stack pre = new Stack<>();

 6

 7 List res = new ArrayList<>();

 8

 9 TreeNode p = root;

10 do {

11 for (TreeNode i = p; i! = null; i = i.left) {

12  res.add(i.val);

13  pre.push(i);

14 }

15 p = pre.pop().right;

16} while (p != null || !pre.empty());

17 return res;

18 }

19 }