java数据结构与算法刷题-----LeetCode144. 二叉树的前序遍历

本文主要是介绍java数据结构与算法刷题-----LeetCode144. 二叉树的前序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

解题思路

1. 利用递归，每次入栈一个结点（每次递归都是一个入栈操作）。然后依次访问左右结点
2. 先序遍历是，先访问当前结点，然后访问左儿子，然后访问右儿子
3. 可以自己创建栈，然后不使用递归

代码

1. 递归
   

/*** 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 {private LinkedList<Integer> list = new LinkedList<>();/**递归先输出自己，然后左子树，然后右子树*/public List<Integer> preorderTraversal(TreeNode root) {if(root == null) return list;list.add(root.val);if(root.left != null) preorderTraversal(root.left);if(root.right != null) preorderTraversal(root.right);return list;}
}

2. 迭代，自己创建栈模拟递归过程
   

class Solution {/**迭代*/public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();//模拟栈LinkedList<Integer> list = new LinkedList<>();//保存答案while(root != null || !stack.isEmpty()){//如果栈不为空，或者当前结点不为空，就还能遍历while(root!=null){//不断访问list.add(root.val);//先访问当前结点stack.push(root);//然后将当前结点入栈root = root.left;//然后访问左子树}root = stack.pop();//然后出栈root = root.right;//访问其右子树}return list;}
}

这篇关于java数据结构与算法刷题-----LeetCode144. 二叉树的前序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---