一段代码让你理解二叉树的递归奥秘

class  TreeNode

{

TreeNode left;

TreeNode right;

int val;

TreeNode(int val){

this.val=val;

}

static void scanNodes(TreeNode root){

if(root!=null){

System.out.println("this is node :"+root.val); //先序遍历

scanNodes(root.left);

System.out.println("node"+root.val+" finish scanning left");

scanNodes(root.right);

System.out.println("node"+root.val+" finish scanning right");

}

}

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);

}

}

运行结果如下：

总体思路就是先左子树，再右子树；左子树上的每个结点都要判断是否有左右孩子，当遍历到左子树的叶子节点时，左子树遍历完毕，开始右子树。