先序遍历

给定一个二叉树的根节点 root ，返回它的 先序 遍历。
先序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树

示例

[二叉树] 系列：非递归先序遍历 - 图1

方法一：递归

  1. class Solution {
  2.     List<Integer> res = new ArrayList<>();
  3.     public List<Integer> preorderTraversal(TreeNode root) {
  4.         if(root == null) return res;
  5.         res.add(root.val);
  6.         preorderTraversal(root.left);
  7.         preorderTraversal(root.right);
  8.         return res;
  9.     }
  10. }

方法二：迭代

1.初始化返回列表，判空，初始化栈，初始化cur节点
2.循环：当前节点不空或者栈不空

  • 从当前节点开始一直往左相继添加到res，同时入栈
  • 出栈，当前节点指向右孩子

3.返回res

  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         if(root == null) return res;
  5.         LinkedList<TreeNode> stack = new LinkedList<>();
  6.         TreeNode cur = root;
  7.         while(cur != null || !stack.isEmpty()){
  8.             while(cur != null){
  9.                 res.add(cur.val);
  10.                 stack.addFirst(cur);
  11.                 cur = cur.left;
  12.             }
  13.             cur = stack.removeFirst();
  14.             cur = cur.right;
  15.         }
  16.         return res;
  17.     }
  18. }

或者：

  1. class Solution {
  2.     List<Integer> res = new ArrayList<>();
  3.     public List<Integer> preorderTraversal(TreeNode root) {
  4.         List<Integer> res = new ArrayList<>();
  5.         if(root == null) return res;
  6.         LinkedList<TreeNode> stack = new LinkedList<>();
  7.         TreeNode cur = root;
  8.         stack.addFirst(cur);
  9.         while(!stack.isEmpty()){
  10.             cur = stack.removeFirst();
  11.             res.add(cur.val);
  12.             if(cur.right != null){    //右
  13.                 stack.addFirst(cur.right);
  14.             }
  15.             if(cur.left != null){     //左
  16.                 stack.addFirst(cur.left);
  17.             }
  18.         }
  19.         return res;
  20.     }
  21. }

方法三：Morris中序遍历

能将非递归的中序遍历空间复杂度降为 O(1)。