二叉树操作

发表于 | 分类于 | 热度:
字数统计: 3k 字 | 阅读时长 ≈ 15 分钟

1. 给定一个字符串求字符串中所有字符组成的全排列即所有字符的组合的情况

例如 abcd 这个字符串，求这四个字符的全排列我们可以这样的进行思考，首先固定第一位的字符，然后把后序的字符依次与第一个位置的字符进行数据位置交换，依次，对于后序的字符我们采用这样方法依次进行交换。按照这种规律，我们可以想到递归的思想。

递归求全排列

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
public static void main(String[] args) {
    String array = "abc";
    char[] chars = array.toCharArray();
    allSort(chars,0,array.length());
}

private static void allSort(char[] array, int start, int end) {
        if (end < 0) {
            return;
        }
        if (start == end) {
            System.out.println(array);
        }else {
            for (int i = start; i < end; i++) {
                swap(array, start, i);
                allSort(array,start+1,end);
                swap(array, i, start);
            }
        }
    }

    private static void swap(char[] array, int start, int i) {
        char temp = array[start];
        array[start] = array[i];
        array[i] = temp;
    }

除了这种方法外，这个题的递归代码还可以这样写：

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

public static void main(String[] args) {
    String array = "abc";
    allZuHe("", array);

}

public static void allZuHe(String a, String b) {
    if (a.length() == 3) {
        System.out.println(a);
    }
    for (int i = 0; i < b.length(); i++) {
        String atemp = a;
        String btemp = b;
        StringBuffer temp = new StringBuffer(b);
        allZuHe(a+temp.charAt(i),temp.deleteCharAt(i).toString());
    }
}

2.求一个连续整数数组中的连续子序列和的最大值

例如在 {-2,-1,6,-3,-2,7,-15,1,2,2} 中连续子序列的最大是8 即是由数组中的 6 -3 -2 7 构成的连续子序列的和最大

我们可以采用 前i项和与第i项进行比较，取前i项和与第i项的最大值。由于我们每一步的最大值都会变，所以我们需要使用一个变量并记录当前计算或者上一步计算中的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class ArraySum {
    public static void main(String[] args) {
        int[] array = {-2,-1,6,-3,-2,7,-15,1,2,2};
        int i = FindGreatestSumOfSubArray(array);
        System.out.println(i);

    }

    public static int FindGreatestSumOfSubArray(int[] array) {
        //max就是上面的dp[i]
        int max = array[0];
        //因为这个dp[i]老是变，所以比如你dp[4]是8 dp[5]就变成-7了，所以需要res保存一下
        int res = array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max + array[i], array[i]);
            res = Math.max(res, max);
        }
        return res;
    }
}

3. 二叉树

给定数组构建二叉树

由数组构建二叉树，主要是按照数组中的数据顺序，把数组中的数据插入到二叉树中。

最重要的就是先找出非叶子节点的节点序号，需要为每个序号建立他们的左右孩子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static TreeNode creatTreeByArray(int[] array) {
    List<TreeNode> treeNodeList = new ArrayList<>();
    for (int i = 0; i < array.length; i++) {
        treeNodeList.add(new TreeNode(array[i]));//把数组转换为树中的节点
    }
    int countNode = array.length; //节点个数
    //为每个父节点添加左右孩子节点
    //父节点的个数为countNode/2   父节点的下标为 countNode - 1
    for (int i = 0; i < countNode / 2 - 1 ; i++) {
        treeNodeList.get(i).left = treeNodeList.get(i * 2 + 1);
        treeNodeList.get(i).right = treeNodeList.get(i * 2 + 2);
    }
    int lastTreeNode = countNode / 2 - 1;
    //如果节点数量为奇数则最后一个父节点有右孩子
    treeNodeList.get(lastTreeNode).left = treeNodeList.get(lastTreeNode * 2 + 1);
    if (countNode % 2 == 1) {
        treeNodeList.get(lastTreeNode).right = treeNodeList.get(lastTreeNode * 2 + 2);
    }

    return treeNodeList.get(0);
}

前序遍历的递归与非递归

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
//前序的非递归与递归
    public static void preePrintNode(TreeNode treeNode) {
        TreeNode node = treeNode;
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack();
        while(node!=null || !stack.empty()){
            if (node != null) {
                System.out.print(node.value+"->");
                stack.push(node);
                node = node.left;
            }else{
                TreeNode pop = stack.pop();
                node = pop.right;
            }
        }
    }

    public static void prePrintNodeDiGui(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        System.out.print(treeNode.value+"->");
        preePrintNode(treeNode.left);
        preePrintNode(treeNode.right);
    }

把 前序遍历的结果存放在集合中

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

//前序遍历存集合中
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorderTree(root,result);
    return result;
}
public void preorderTree(TreeNode root,List<Integer> list){
    if (root==null){
        return ;
    }
    list.add(root.value);
    preorderTree(root.left,list);
    preorderTree(root.right,list);
}

//前序遍历非递归集合
public List<Integer> preorderList(TreeNode root){
    List<Integer> result = new ArrayList<>();
    TreeNode node = root;
    Stack<TreeNode> stack = new Stack();

    while (node != null || !stack.empty()) {
        if (node != null) {
            result.add(node.value);
            stack.push(node);
            node = node.left;
        }else {
            TreeNode pop = stack.pop();
            node = pop.right;
        }
    }
    return result;
}

中序遍历的递归与非递归

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

//中序的非递归与递归
public static void middlePrintNode(TreeNode treeNode) {
    TreeNode node = treeNode;
    if (treeNode == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    while (node != null || !stack.empty()) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        }else {
            TreeNode pop = stack.pop();
            System.out.print(pop.value+"->");
            node = pop.right;
        }
    }
}

//递归
public static void middlePrintNodeDiGui(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }
    middlePrintNodeDiGui(treeNode.left);
    System.out.print(treeNode.value+"->");
    middlePrintNodeDiGui(treeNode.right);
}

后序遍历的递归与非递归

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
59
60
61
62
63
64
65
66

//后序遍历的非递归
public static void houPrintNode(TreeNode treeNode) {
    TreeNode node = treeNode;
    TreeNode curnode = null;
    if (treeNode == null) {
        return;
    }
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(node);
    //stack2 按照根右左的顺序进栈
    while (!stack1.empty()) {
        curnode = stack1.pop();
        stack2.push(curnode);
        if (curnode.left != null) {
            stack1.push(curnode.left);
        }
        if (curnode.right != null) {
            stack1.push(curnode.right);
        }
    }
    while (!stack2.empty()) {
        System.out.print(stack2.pop().value+"->");
    }

}


//后序非递归集合---把结果存放在集合中

public static List<Integer> houPrintTreeList(TreeNode treeNode) {
    TreeNode node = treeNode;
    List<Integer> result = new ArrayList<>();
    if (node == null) {
        return result;
    }
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(node);
    while (!stack1.empty()) {
        TreeNode curNode = stack1.pop();
        stack2.push(curNode);
        if (curNode.left != null) {
            stack1.push(curNode.left);
        }
        if (curNode.right != null) {
            stack1.push(curNode.right);
        }
    }
    while (!stack2.empty()) {
        result.add(stack2.pop().value);
    }
    return result;
}


//后序遍历递归实现
public static void houPrintNodeDiGui(TreeNode treeNode) {
    if (treeNode == null) {
        return;
    }
    houPrintNodeDiGui(treeNode.left);
    houPrintNodeDiGui(treeNode.right);
    System.out.print(treeNode.value+"->");
}

给定二叉树，返回层次遍历得到的节点

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

//层次[[],[],[]]
//给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
public static List<List<Integer>> cengciPrintNode(TreeNode treeNode) {
    List<List<Integer>> result = new ArrayList<>();
    if (treeNode == null) {
        return result;
    }
    Queue<TreeNode> queue = new ArrayDeque<>();
    //Queue<TreeNode> queue2 = new ArrayDeque<>();
    queue.offer(treeNode);
    int count = 0;
    while (!queue.isEmpty()) {
        List list = new ArrayList();
        count = queue.size();
        for (int i = 0; i < count; i++) {
            TreeNode poll = queue.poll();
            list.add(poll.value);
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        result.add(list);
    }
    return result;
}
二叉树，从最底层向上，依次层次遍历
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

//从底向上遍历
//给定一个二叉树，返回其节点值自底向上的层次遍历。
// （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
public static List<List<Integer>> downToUpCengCiPrint(TreeNode root){
    LinkedList<List<Integer>> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    int count = 0;
    while (!queue.isEmpty()) {
        List list = new ArrayList();
        count = queue.size();
        for (int i = 0; i < count; i++) {
            TreeNode temp = queue.poll();
            list.add(temp.value);
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
        result.addFirst(list);
    }
    return result;
}

求树的路径的和

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

public class TreeSumPath {
    public static void main(String[] args) {
        TreeDemo treeDemo = new TreeDemo();
        int[] array = {12,8,6,16,20,22,18};
        TreeNode treeNode = treeDemo.creatBinTree(array);
        List<List<Integer>> path = findPath(treeNode, 36);
        System.out.println(path.toString());
        int pathSum = findPathSum(treeNode);
        System.out.println(pathSum);
    }

    //找二叉树中存在目标值得节点，并打印出路径
    public static void treesumPath(TreeNode treeNode,int target) {
        if (treeNode == null) {
            return;
        }
        ArrayList list = new ArrayList();
        printPath(treeNode, target, list);
    }

    public static void printPath(TreeNode treeNode, int target, ArrayList list) {
        if (treeNode == null) {
            return;
        }
        list.add(treeNode.value);
        target = target - treeNode.value;
        if (target == 0 && treeNode.left == null && treeNode.right == null) {
            for (Object integer : list) {
                System.out.print(integer + " ->");
            }
            System.out.println();
        } else {
            printPath(treeNode.left, target, list);
            printPath(treeNode.right, target, list);
        }
        list.remove(list.size() - 1);
    }
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，
// 这条路径上所有节点值相加等于目标和。
public static boolean hasPathSum(TreeNode root, int sum) {
    if(root == null){
        return false;
    }
    sum = sum - root.value;
    if(root.left == null && root.right == null){
        return sum == 0;
    }else{
        return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
    }
}

这条路径上所有节点值相加等于目标的目标路径 返回List<List>

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

//给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，
// 这条路径上所有节点值相加等于目标的目标路径 返回List<List<Integer>。
public static List<List<Integer>> findPath(TreeNode root,int target){
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    if (root == null) {
        return result;
    }
    getPath(root, target, result, temp);
    return result;
}

public static void getPath(TreeNode treeNode, int target, List<List<Integer>> result, List<Integer> temp) {
    if (treeNode == null) {
        return;
    }
    target = target - treeNode.value;
    if (treeNode.left == null && treeNode.right == null) {
        if (target == 0) {
            temp.add(treeNode.value);
            result.add(new ArrayList<>(temp));
            temp.remove(temp.size() - 1);
        }
        return;
    }else {
        if (treeNode.left != null) {
            temp.add(treeNode.value);
            getPath(treeNode.left,target,result,temp);
            temp.remove(temp.size() - 1);
        }
        if (treeNode.right != null) {
            temp.add(treeNode.value);
            getPath(treeNode.right, target, result, temp);
            temp.remove(temp.size() - 1);
        }
    }
}

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

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

    //给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
    //首先找出所有的从根节点带叶子节点的所有路径
    //求所有路径组成的数字并求和
    public static int findPathSum(TreeNode treeNode) {
        int result = 0;
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        findPathList(treeNode, resultList, temp);
        System.out.println(resultList.toString());
        for (List list: resultList) {
            StringBuffer stringBuffer = new StringBuffer();
            for (int i = 0; i < list.size(); i++) {
                stringBuffer.append(list.get(i).toString());
            }
            int t = Integer.parseInt(stringBuffer.toString());
            result += t;
        }
        return result;
    }

    private static void findPathList(TreeNode treeNode, List<List<Integer>> resultList, List<Integer> temp) {
        if (treeNode == null) {
            return;
        }
        if (treeNode.left == null && treeNode.right == null) {
            temp.add(treeNode.value);
            resultList.add(new ArrayList<>(temp));
            temp.remove(temp.size() - 1);
        }else {
            if (treeNode.left != null) {
                temp.add(treeNode.value);
                findPathList(treeNode.left, resultList, temp);
                temp.remove(temp.size() - 1);
            }
            if (treeNode.right != null) {
                temp.add(treeNode.value);
                findPathList(treeNode.right, resultList, temp);
                temp.remove(temp.size() - 1);
            }
        }

    }


}

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

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
package com.data.treeDemo;


import com.data.TreeNode;

/**
 * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
 *
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
 *
 * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
 */

/**
 * 二叉搜索树的中序遍历就是升序排列的
 * 所以升序数组是树的中序遍历
 * 用二分法加递归就可以构建二叉树
 *
 * 从定义我们知道，二叉搜索树的中序遍历为一个递增序列，给定的数组其实就是中序遍历结果
 * 取有序数组的中间值做根，左边部分做左树，右边部分做右树如此循环迭代去二分就可还原这棵BST树
 */
public class tranSearchTree {
    public static void main(String[] args) {
        int[] array = {-10,-3,0,5,9};
    }

    public TreeNode createSearchTree(int[] array,int start,int end){
        if (array == null || array.length == 0) {
            return null;
        }
        //计算中间节点
        int middle = start + (end - start) / 2;
        TreeNode root = new TreeNode(array[middle]);
        root.left = createSearchTree(array, start, middle);
        root.right = createSearchTree(array, middle, end);
        return  root;
    }




}

本文标题:二叉树操作

文章作者:雷凯博

发布时间:2020年06月12日 - 20:06

最后更新:2021年05月16日 - 19:05

原始链接:http://yoursite.com/2020/06/12/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%93%8D%E4%BD%9C/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

坚持原创技术分享，您的支持将鼓励我继续创作！
-------------本文结束感谢您的阅读-------------
0%