【递归】 144 二叉树的前序遍历

题目

给定一个二叉树返回他的前序遍历 输入: [1,null,2,3] 1 2 / 3 输出: [1,2,3]

思路

前序和中序遍历只需要改变一下记录根节点的顺序。 非递归的写法就是设置一个栈，按照（根，右，左）的顺序放入，最后的输出就是根左右

代码

递归：

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); helper(root,res); return res; } public void helper(TreeNode root,List<Integer> res ){ if(root!=null){ res.add(root.val); if(root.left!=null){ helper(root.left,res); } if(root.right!=null){ helper(root.right,res); } } }

非递归：

public static void preOrderUnRecur(Node head) { System.out.print("pre-order: "); if (head != null) { Stack<Node> stack = new Stack<Node>(); stack.add(head); while (!stack.isEmpty()) { head = stack.pop(); System.out.print(head.value + " "); if (head.right != null) { stack.push(head.right); } if (head.left != null) { stack.push(head.left); } } } System.out.println(); }