LeetCode.144. 二叉树的前序遍历

题目

144. 二叉树的前序遍历

分析

这道题目是比较基础的题目，我们首先要知道二叉树的前序遍历是什么？
就是【根 左 右】 的顺序，然后利用递归的思想，就可以得到这道题的答案，任何的递归都可以采用 栈 的结构来实现，所以我会写两种方式来解决这道题目。

代码

递归版本

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();func(root,res);return res;}void func(TreeNode cur,List<Integer> res) {if(cur == null) return;// 先记录根节点res.add(cur.val);// 遍历左子树func(cur.left,res);// 遍历右子树func(cur.right,res);}
}

非递归版本

需要借助栈这种数据结构，先把根节点入栈，判断栈是否为空，不为空弹出来栈顶元素，栈顶元素不为空，先把右子树加入栈里面，再把左子树加入栈里面，为空继续遍历栈。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> s = new Stack<>();s.push(root);while(!s.isEmpty()) {TreeNode node = s.pop();if(node != null) {res.add(node.val);}else {continue;}s.push(node.right);s.push(node.left);}return res;}}