java二叉树漫谈--二叉树的递归便利和路径_二叉树的便利

假设有一个二叉树如图所示：

这是最常见的一种结构，首先看java中定义二叉树结构的方法，首先这个类中必须有三个要素，左子树、右子树、节点上的值。

public class MyTreeNode {

    public int val;
    public MyTreeNode left;
    public MyTreeNode right;

    public MyTreeNode(int val, MyTreeNode left, MyTreeNode right){
        this.val =val;
        this.left = left;
        this.right = right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

谈到二叉树 必然会涉及到二叉树的便利，二叉树的便利主要有三种，先序便利、中序便利、后序便利，三种便利的区别是先处理那个节点的区别，三种便利的输出结果：

• 中序便利：124536
• 先序便利：425136
• 后序便利：452631

二叉树三种便利在java中是实现代码是一样的，只是处理子节点值的位置不一样，核心算法采用递归实现最简单易懂，当然有非递归的效率更高的实现。

 /** 
     * 先序遍历 
     *  
     * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void preOrderTraverse(MyTreeNode node) {  
        if (node == null)  
            return;  
        System.out.print(node.data + " ");  
        preOrderTraverse(node.left);  
        preOrderTraverse(node.right);  
    }  

    /** 
     * 中序遍历 
     *  
     * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void inOrderTraverse(MyTreeNode node) {  
        if (node == null)  
            return;  
        inOrderTraverse(node.left);  
        System.out.print(node.data + " ");  
        inOrderTraverse(node.right);  
    }  

    /** 
     * 后序遍历 
     *  
     * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void postOrderTraverse(MyTreeNode node) {  
        if (node == null)  
            return;  
        postOrderTraverse(node.left);  
        postOrderTraverse(node.right);  
        System.out.print(node.data + " ");  
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

二叉树中的第二个关键就是获取二叉树路径的问题：
java获取二叉树中所有路径集合的算法：

  public List<String> binaryTreePaths(MyTreeNode root) {  
        List<String> answer = new ArrayList<String>();  
        if (root != null) searchBT(root, "", answer);  
        return answer;  
    }  

    private void searchBT(MyTreeNode root, String path, List<String> answer) {  
        if (root.left == null && root.right == null) answer.add(path + root.val);  
        if (root.left != null)  searchBT(root.left, path + root.val + "-", answer);  
        if (root.right != null) searchBT(root.right, path + root.val + "-", answer);  
    }
1
2
3
4
5
6
7
8
9
10
11

这个算法本质上基本就是便利二叉树，但是会单独处理经过节点的路径。