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 ListpreorderTraversal(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 Stackpre = new Stack<>();
6
7 Listres = 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 ListpreorderTraversal(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 Stackpre = new Stack<>();
6
7 Listres = 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 }