算法（三）

1、二叉树深度优先遍历、广度优先遍历

二叉树深度优先遍历（前序、中序、后序），此处采用中序。代码如下：

#递归版本

public void inOrderTraverse1(TreeNode root){

if(root!=null){

System.out.print(root.val);

inOrderTraverse1(root.left);

inOrderTraverse1(root.right);

}

}

#非递归版本

public void preOrderTraverse2(TreeNode root) {  

LinkedList<TreeNode> stack = new LinkedList<>();  

    TreeNode pNode = root;  

    while (pNode != null || !stack.isEmpty()) {  

     if (pNode != null) {  

         System.out.print(pNode.val+"  ");  

            stack.push(pNode);  

            pNode = pNode.left;  

        } else if(pNode == null && !stack.isEmpty()){

         TreeNode node = stack.pop();  

            pNode = node.right;  

        }  

    }  

}  

#二叉树广度优先遍历(层次遍历)，代码如下：

public void levelTraverse(TreeNode root){

if(root == null){

return;

}

LinkedList<TreeNode> queue = new LinkedList<>();

queue.offer(root);

while(!queue.isEmpyt()){

TreeNode node = queue.poll();

System.out.print(node.val +“ ”);

if(node.left != null){

queue.offer(root.left);

}

if(node.right != null){

queue.offer(root.right);

}

}

}

#二叉树广度优先遍历(层次遍历)，代码如下：

public void depthOrderTraverse(TreeNode root) {  

        if (root == null) {  

            return;  

        }  

        LinkedList<TreeNode> stack = new LinkedList<>();  

        stack.push(root);  

        while (!stack.isEmpty()) {  

            TreeNode node = stack.pop();  

            System.out.print(node.val+"  ");  

            if (node.right != null) {  

                stack.push(node.right);  

            }  

            if (node.left != null) {  

                stack.push(node.left);  

            }  

        }