二叉树的注意事项_二叉树注意点

注意一：二叉树解题的思维模式分两类

1：是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2：是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

后序位置的特殊之处

这里面大有玄妙，意味着前序位置的代码只能从函数参数中获取父节点传递来的数据，

而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。

换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

如果前序位置，中序位置为空，只有后序位置不为空。那么递归直接来到尾部，然后从后往前处理和判断数据。

例子：把根节点看做第 1 层，如何打印出每一个节点所在的层数？

public class tree5 {
    public void print(TreeNode root){
        traverse(root, 1);
    }

    void traverse(TreeNode root, int level){
        if(root == null){
            return;
        }
        System.out.println(level);
        traverse(root.left,level+1);
        traverse(root.right,level+1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

采用的是前序位置

注意：level 一直是 1 ，没有level = level + x ;

2: 如何打印出每个节点的左右子树各有多少节点？

public class Tree6 {
    public int count(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftCount = count(root.left);
        int rightCount = count(root.right);
        System.out.println("左子树有"+leftCount+"右子树有"+rightCount);
        return leftCount + rightCount + 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

注意：

return leftCount + rightCount + 1;
1

当思考一号节点思考不出来返回什么到底，那就将目光放在2号节点，2号是左子树的根，要返回的应该是左子树的所有节点的个数，

再根据递归的思想，他也有leftcount 和 rightcount ,所以返回的应该是 leftCount + rightCount + 1;

注意二： 二叉树的基本操作

1：获取叶子节点的个数

   //遍历的方法
    int size = 0;
    int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        if(root.left == null && root.right == null){
            size++;
        }
        return size;
    }
    
//子问题的方法

    //思路：刚上来：头节点叶子的个数：是左子树叶子的个数 + 右子树叶子的个数
    int getLeafNodeCount2(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        int leftCont = getLeafNodeCount2(root.left);
        int rightCount = getLeafNodeCount2(root.right);

        //不是叶子节点的话，就返回左子树的叶子数与右子树叶子数的和
        return leftCont + rightCount;
    }
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

2：获取第K层节点的个数

//遍历的方法
    public static int depth = 0;
    public static int sizes = 0;
    int getKLevelNodeCount(TreeNode root, int k){
        if(root == null){
            //     楼梯往上走
            return 0;
        }
        depth++;
        if(depth == k){
            sizes++;
            depth--;
            return sizes;
        }
        //     楼梯往下走
        getKLevelNodeCount(root.left, k);
        getKLevelNodeCount(root.right, k);
        depth--;
        //     楼梯往上走
        return sizes;
    }

//子问题的方法

    /**
     * 左子树当中K节点的个数 + 右子树当中K节点的个数
     */
    public static int dep = 0;
    int getKLevelNodeCount2(TreeNode root, int k){
        if(root == null){
            return 0;
        }
        dep++;
        if(dep == k){
            dep--;
            return 1;
        }
        //     楼梯往下走
        int leftCount = getKLevelNodeCount2(root.left, k);
        int rightCount = getKLevelNodeCount2(root.right, k);
        dep--;
        return leftCount + rightCount;
    }

//子问题的方法  方法二
    public static int s = 0;
    int getKLevelNodeCount3(TreeNode root, int k){
        if(root == null ){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        int leftCount = getKLevelNodeCount3(root.left , k-1); //注意K-1
        int rightCount = getKLevelNodeCount3(root.right , k-1);
        return leftCount + rightCount;
    }
}
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
48
49
50
51
52
53
54
55
56
57
58

3：获取二叉树的高度

//子问题方法：求出左子树的高度和右子树的高度，算出最大值，然后加1。
    int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftCount = getHeight(root.left);
        int rightCount = getHeight(root.right);
        int max = leftCount > rightCount ? leftCount : rightCount;
        return max + 1;
    }
1
2
3
4
5
6
7
8
9
10

//遍历的方法
    static int size = 0;
    int max = 0;
    int getHeight2(TreeNode root){
        if(root == null){
            return 0;
        }
        size++;
        getHeight2(root.left);
        getHeight2(root.right);
        if(root.left == null && root.right == null){
            if(size > max){
                max = size;
            }
        }
        size--;
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4：检测值为value的元素是否存在

    TreeNode ret = null;
    TreeNode find(TreeNode root, int val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode ret = find(root.left , val);
        if(ret != null){
            return ret;
        }
        TreeNode ret2 = find(root.left , val);
        if(ret2 != null){
            return ret2;
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5：二叉树的层序遍历

public void func1(TreeNode root){
        if (root == null) {
            return;
        }
        //  创建一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        //  先把队列的头给放进去
        queue.offer(root);

        while (!queue.isEmpty()) {
            // 通过一个中间变量cur从而实现层序的构建
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            // 加入判断条件
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

6：二叉树的前序遍历创建

读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储），然后再以中序遍历的顺序打印出来。

import java.util.Scanner;

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;
    TreeNode(char val) {
        this.val = val;
    }
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();//支持空格的输入
            TreeNode root = main.createTree(str); //根据字符串构建一个二叉树
            main.inorder(root);//根据二叉树的根节点中序打印这个二叉树
        }
    }
    //中序遍历
    public void inorder (TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    //根据字符串创建二叉树
    int i = 0;//                                                          注意
    public TreeNode createTree (String str) {
        TreeNode cur = null;
        if (str.charAt(i) != '#') {
            cur = new TreeNode(str.charAt(i));
            i++;
            cur.left = createTree(str);
            cur.right = createTree(str);

        } else {
            i++;
        }
        return cur;
    }
}

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
48
49

注意1：int i = 0 比用 static int i = 0 要好，因为当Main这个类构造很多的对象时,很多对象的起始 i 不是0了；

注意2：i不可以放在createTree方法里面，因为递归返回，然后再进入右侧分支的时候i可能从0开始，而不是我们预期的下标。

注意3：至于i 最后指向了字符串str最后一个字符的后面，但是递归已经结束了，所以至于i在哪已经不重要了。