Java二叉树的前相遍历(递归/非递归)前相遍历码实现递归方式非递归方式
简介：遍历是对树的最基本运算。 遍历二叉树是指按一定的规则和顺序遍历二叉树的所有节点，使每个节点只访问一次，而且只访问一次。
假设l、d和r分别表示左子树的遍历、对根节点的访问以及对右子树的遍历，则对一个二叉树的遍历包括DLR (被称为前向遍历(，LDR )、中序遍历)
向前遍历向前遍历：首先访问当前节点，然后递归访问该节点左侧的子树，最后递归访问该节点右侧的子树。
图中所示二叉树的前序扫描的结果是[3、9、8、20、15、4、7]
实现代码递归方式的publiclistintegerpreordertraversal (treenode root ) listintegerpre=newlinkedlistinteger )； pre helper (根，预)； 返回前； } publicvoidprehelper (趋势根，列表integer pre ) if ) root==null ) return； pre.add (根. val； pre helper (根. left，pre )； pre helper (根. right，pre )； }非递归方式publiclistintegerpreordertraversal (treenode root ) { StackTreeNode stack=new Stack )； 列表integer list=new ArrayList (； TreeNode cur=root； while (！ stack.isempty(||cur！=null(while(cur！=null}{list.add(cur.val )； 堆叠. push (cur； cur=cur.left； } cur=stack.pop (； cur=cur.right； }返回列表； }完整代码：
publicstaticvoidmain (字符串[ ] args ) treenoderoot=newtreenode ) 3； treenodeN1=newtreenode(9； treenodeN2=newtreenode(20； treenodeN3=newtreenode(8； treenodeN4=newtreenode(15； treenodeN5=newtreenode(7； treenodeN6=newtreenode(4； 根. left=n1； root.right=n2； n1.right=n3； n2.left=n4； n2.right=n5； n4.left=n6； listintegerrs=前序遍历(根)； 递归前向遍历结果： ' rs )； RS=preorder traversal2(根； 系统. out.println (非递归渐进遍历结果： ' rs )； //递归publicstaticlistintegerpreordertraversal (趋势根) {列表integer pre=new ArrayList )； pre helper (根，预)； 返回前； } publicstaticvoidprehelper (treenode root，列表integer pre ) if ) root==null ) { return； }pre.add(root.val )； pre helper (根. left，pre )； pre helper (根. right，pre )； //非递归publicstaticlistintegerpreordertraversal2(treenode root ) { StackTreeNode stack=new Stack； 列表integer list=new ArrayList (； TreeNode cur=root； while (！ stack.isempty(||cur！=null(while(cur！=null}{list.add(cur.val )； 堆叠. push (cur； cur=cur.left； } cur=stack.pop (； cur=cur.right； }返回列表； }执行结果：