卓越飞翔博客二叉树是由n个结点构成的有限集合，n=0时为空树，n>0时为非空树。
非空树：
有且仅有一个根结点；
除根结点外的其余结点又可分为两个不相交的子集Left 和Right ,分别称为此二叉树的左子树和右子树，且Left 和Right 本身又都是二叉树
2、二叉树的遍历
先序遍历 -- 根左右
中序遍历 -- 左根右
后序遍历 -- 根左右
3、代码实现
public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; } public class Solution { /** * * [url=home.php?mod=space&uid=952169]@Param[/url] root TreeNode类 the root of binary tree * [url=home.php?mod=space&uid=155549]@Return[/url] int整型二维数组 */ public int[][] threeOrders (TreeNode root) { // write code here //创建三个集合，分别用来存放先序、中序、后序 List<Integer> front =new ArrayList<>(); List<Integer> middle =new ArrayList<>(); List<Integer> back = new ArrayList<>(); preOrder (root,front); inOrder (root,middle); postOrder(root,back); System.out.println(front); System.out.println(middle); System.out.println(back); //使用二维数组来接收 int [][] res =new int [3][front.size()]; for(int i = 0; i<front.size();i++){ res[0][i] = front.get(i); res[1][i] = middle.get(i); res[2][i] = back.get(i); } //结果返回二维数组形式 return res; } //先序遍历 -- 根 左 右 public void preOrder(TreeNode root ,List<Integer> list){ if(root == null){ return ; } //先放根节点 list.add(root.val); //递归把左节点的值放入list preOrder(root.left,list); //递归把右节点的值放入list preOrder(root.right,list); } //中序遍历 -- 左 根 右 public void inOrder(TreeNode root ,List<Integer> list){ if(root ==null){ return; } //先放左节点 inOrder(root.left,list); //根节点 list.add(root.val); //右节点 inOrder(root.right,list); } //后序遍历 -- 左 右 根 public void postOrder(TreeNode root ,List<Integer> list){ if(root ==null){ return; } //先放左节点 postOrder(root.left,list); //右节点 postOrder(root.right,list); //根节点 list.add(root.val); } } |
