网站设计制作新报价图片,域名是什么有什么用,网站管理公司,自定义网址生成器文章目录 题目描述递归方法代码 非递归方法代码 题目描述
给你二叉树的根节点 root #xff0c;返回它节点值的 前序 遍历。
示例 1#xff1a;
输入#xff1a;root [1,null,2,3] 输出#xff1a;[1,2,3] 示例 2#xff1a;
输入#xff1a;root [] 输出#xf… 文章目录 题目描述递归方法代码 非递归方法代码 题目描述
给你二叉树的根节点 root 返回它节点值的 前序 遍历。
示例 1
输入root [1,null,2,3] 输出[1,2,3] 示例 2
输入root [] 输出[] 示例 3
输入root [1] 输出[1] 示例 4
输入root [1,2] 输出[1,2] 示例 5
输入root [1,null,2] 输出[1,2]
提示
树中节点数目在范围 [0, 100] 内 -100 Node.val 100
进阶递归算法很简单你可以通过迭代算法完成吗
递归方法
递归的第一步就是找到递归出口这里是root为null的时候结束递归因为如果root为null则既没有val也没有子树所以就不需要继续往下递归了。 接下来就是按照需要遍历的顺序来执行此方法大部分时候不要深入考虑递归的具体实现因为越是考虑越是混乱直接按照顺序交给计算机去执行就可以了。
代码
class Solution {//使用递归的方法来进行前序遍历public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();preorder(root,result);return result;}public void preorder(TreeNode root,ListInteger result){//递归出口if (rootnull) {return;}//遍历中间节点result.add(root.val);//遍历左孩子preorder(root.left,result);//遍历右孩子preorder(root.right,result);}
}非递归方法
思路在代码中详细注释了
代码
class Solution {//使用非递归的方法来完成public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();preorder(root,result);return result;}public void preorder(TreeNode root,ListInteger result){//如果root为空则直接返回if (rootnull){return;}//前序遍历需要把当前节点遍历完再把左子树都遍历完之后再开始遍历右子树//每个节点都是这样的顺序所以需要保存记录当前节点的右孩子因为需要左子树都遍历完才轮到右孩子//考虑使用栈的方法因为栈可以先把一部分暂时不用的信息保存到栈中StackTreeNode stack new Stack();//先把root入栈stack.push(root);//循环遍历直到所有节点都完成遍历while (!stack.isEmpty()){TreeNode treeNode stack.pop();result.add(treeNode.val);//将右孩子入栈再将左孩子入栈这样出栈之后才是左孩子优先if(treeNode.right!null){//如果是空的就不需要入栈了stack.push(treeNode.right);}//将左孩子入栈if(treeNode.left!null){stack.push((treeNode.left));}}}
}
