分别按照二叉树先序，中序和后序打印所有的节点。
输入：
{1,2,3}
输出：
[[1,2,3],[2,1,3],[2,3,1]]
解题思路：
1.递归遍历法；
2.迭代遍历法。
实现代码：
importjava.util.LinkedList;importjava.util.List;importjava.util.Stack;/***
Type类*Description：二叉树先序，中序和后序遍历*Date：/1/:48*/publicclassBTreeReviews{publicstaticvoidmain(String[]args){TreeNoderoot=newTreeNode(1,newTreeNode(2,null,null),newTreeNode(3,null,null));int[][]res=threeOrders(root);System.out.println(res);for(inti=0;i3;i++){for(intj=0;jres.length;j++){System.out.print(res[j]);}System.out.print("\n");}}/****paramrootTreeNode类therootofbinarytree*returnint整型二维数组*/publicstaticint[][]threeOrders(TreeNoderoot){//writecodehereintcount=countNodes(root);ListIntegerpreRes=newLinkedListInteger();preViewsByIterator(root,preRes);ListIntegermidRes=newLinkedListInteger();midViewsByIterator(root,midRes);ListIntegerafterRes=newLinkedListInteger();afterViewsByIterator(root,afterRes);int[][]res=newint[3][count];for(inti=0;icount;i++){res[0]=preRes.get(i);res[1]=midRes.get(i);res[2]=afterRes.get(i);}returnres;}/**获取节点个数，用以声明数组*/privatestaticintcountNodes(TreeNoderoot){if(root==null){return0;}if(root.left==nullroot.right==null){return1;}return1+countNodes(root.left)+countNodes(root.right);}/**先序遍历(递归)*/privatestaticvoidpreViews(TreeNoderoot,ListIntegerres){if(root==null){return;}res.add(root.val);preViews(root.left,res);preViews(root.right,res);}/**先序遍历(迭代)*/privatestaticvoidpreViewsByIterator(TreeNoderoot,ListIntegerres){/**利用栈迭代*1.根节点入栈*2.当栈非空时，栈顶出栈，把出栈的节点值添加到list结尾，然后依次再入栈其右子节点和左子节点*/if(root==null){return;}StackTreeNodestk=newStackTreeNode();TreeNodenode=root;//迭代节点stk.push(node);while(!stk.isEmpty()){node=stk.pop();res.add(node.val);if(node.right!=null){stk.push(node.right);}if(node.left!=null){stk.push(node.left);}}}/**中序遍历（递归）*/privatestaticvoidmidViews(TreeNoderoot,ListIntegerres){if(root==null){return;}midViews(root.left,res);res.add(root.val);midViews(root.right,res);}/**中序遍历（迭代）*/privatestaticvoidmidViewsByIterator(TreeNoderoot,ListIntegerres){/***1.根节点入栈*2.初始化curr为root*3.当栈非空或curr非null时，循环*3.1cur!=null时，说明还有左子节点存在，入栈，并且cur置为自己的左子节点*3.2cur==null时，说明到树最左的节点了，栈顶节点出栈，cur置为栈顶节点的右子节点*/if(root==null){return;}StackTreeNodestk=newStackTreeNode();TreeNodenode=root;//迭代节点while(!stk.isEmpty()node!=null){if(node!=null){stk.push(node);node=node.left;}else{//如果curr==null代表向左遍历到头了或者刚弹出的元素无右孩子//弹出栈顶元素入列(或打印)然后向右node=stk.pop();res.add(node.val);node=node.right;}}}/**后序遍历(递归)*/privatestaticvoidafterViews(TreeNoderoot,ListIntegerres){if(root==null){return;}afterViews(root.left,res);afterViews(root.right,res);res.add(root.val);}/**后序遍历(迭代)*/privatestaticvoidafterViewsByIterator(TreeNoderoot,ListIntegerres){if(root==null){return;}StackTreeNodestk=newStackTreeNode();TreeNodenode=root;//迭代节点stk.push(node);while(!stk.isEmpty()){node=stk.pop();res.add(0,node.val);if(node.left!=null){stk.push(node.left);}if(node.right!=null){stk.push(node.right);}}}}classTreeNode{intval=0;TreeNodeleft=null;TreeNoderight=null;publicintgetVal(){returnval;}publicvoidsetVal(intval){this.val=val;}publicTreeNodegetLeft(){returnleft;}publicvoidsetLeft(TreeNodeleft){this.left=left;}publicTreeNodegetRight(){returnright;}publicvoidsetRight(TreeNoderight){this.right=right;}publicTreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}预览时标签不可点收录于话题#个上一篇下一篇