LeetCode Java刷题笔记—144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

简单难度。先访问根节点，再前序遍历左子树，再前序遍历右子树。

最简单的就是使用递归的方式。

public List<Integer> preorderTraversal( TreeNode root ){
          
   

   ArrayList<Integer> lists = new ArrayList();
   preorder( root, lists );
   return lists;
}

private void preorder( TreeNode root, List<Integer> lists ){
          
   

   if( root == null ){
          
   
      return;
   }
   lists.add( root.val );
   preorder( root.left, lists );
   preorder( root.right, lists );
}

另一种非递归的方式，这种方式最好也要掌握。因为一般出到这种简单题的时候，可能会让你用非递归的方法写。

我们这里借助栈结构实现前序遍历。

public List<Integer> preorderTraversal( TreeNode root ){
          
   

   List<Integer> result = new ArrayList<>();
   if( root == null ){
          
   
      return result;
   }
   //使用LinkedList模拟栈结构
   LinkedList<TreeNode> treeNodes = new LinkedList<>();
   //头节点先入栈
   treeNodes.addFirst( root );
   while( !treeNodes.isEmpty() ){
          
   
      //出栈
      root = treeNodes.removeFirst();
      result.add( root.val );
      if( root.right != null ){
          
   
         //右子节点先入栈
         treeNodes.addFirst( root.right );
      }
      if( root.left != null ){
          
   
         //左子节点后入栈
         treeNodes.addFirst( root.left );
      }
   }
   return result;
}