二叉树的递归遍历以及最大深度的求解（南京Java工程师培训.doc

二叉树的递归遍历以及最大深度的求解（南京Java工程师培训）递归是非常神奇的方法，代码看起来很简洁。对二叉树的遍历和求最大深度可以用递归的方法，主要思路就是遍历左子树，再遍历右子树。如果左子树上面的结点，有右孩子，则调用右子树的方法；遍历到左子树的叶节点的时候，返回，开始遍历右子树。如果右子树上面的结点有左孩子，则调用左子树的方法，遍历到右子树的叶子结点的时候，程序结束。static void scanNodes（TreeNode root）if（root=null）return;System.out.println（root.val）； /先序遍历scanNodes（root.left）；/System.out.println（root.val）； 中序遍历scanNodes（root.right）；/System.out.println（root.val）； 后序遍历求二叉树的最大深度，也是这个思路，只需添加个返回值即可static int getDepth（TreeNode root）if（root=null）return 0;int left=getDepth（root.left）；int right=getDepth（root.right）；return leftright?left+1:right+1;下面附上，完整的测试代码，里面有二叉树结点的定义，大家一看就懂class TreeNodeTreeNode left;TreeNode right;int val;TreeNode（int val）this.val=val;/返回二叉树的深度static int getDepth（TreeNode root）if（root=null）return 0;int left=getDepth（root.left）；int right=getDepth（root.right）；return leftright?left+1:right+1;static void scanNodes（TreeNode root）if（root=null）return;System.out.println（root.val）； /先序遍历scanNodes（root.left）；/System.out.println（root.val）； 中序遍历scanNodes（root.right）；/System.out.println（root.val）； 后序遍历public static void main（String args）TreeNode root=new TreeNode（1）；TreeNode left1=new TreeNode（2）；TreeNode left2=new TreeNode（3）；TreeNode right1=new TreeNode（4）；/创建一棵树root.left=left1;left1.right=left2;root.right=right1;scanNodes（root）；System.out.println（树的深度是：+getDepth（root）；运行结果如下：1234树的深度是