BinaryTree
Kang Lv3
 2021-12-26 22:27:18      3.3k 字  16 分钟  

二叉树

二叉树是一种典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

基础知识

树的遍历

前序：根左右；中序：左根右；后序：左右根；

144 94 145

递归

自顶向下

“自顶向下” 意味着在每个递归层级，我们将首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。 所以 “自顶向下” 的解决方案可以被认为是一种前序遍历。

1
2
3
4
5
6
7
8
9
10
11
private int answer;  // don't forget to initialize answer before call maximum_depth
private void maximum_depth(TreeNode root, int depth) {
    if (root == null) {
        return;
    }
    if (root.left == null && root.right == null) {
        answer = Math.max(answer, depth);
    }
    maximum_depth(root.left, depth + 1);
    maximum_depth(root.right, depth + 1);
}
自底向上

在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。 这个过程可以看作是后序遍历的一种。

1
2
3
4
5
6
7
8
public int maximum_depth(TreeNode root) {
 if (root == null) {
  return 0;                                   // return 0 for null node
 }
 int left_depth = maximum_depth(root.left);
 int right_depth = maximum_depth(root.right);
 return Math.max(left_depth, right_depth) + 1; // return depth of the subtree rooted at root
}

104 101

快速排序

快速排序就是个二叉树的前序遍历。

算法思路及原理
  1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。
  2. 将大于分界值的数据集中到数组右边，小于或等于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于分界值。
  3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
  4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了
快排的代码框架
1
2
3
4
5
6
7
8
9
void sort(int[] arr, int left, int right) {
    /****** 前序遍历位置 ******/
    // 通过交换元素构建分界点 p
    int mid = partition(arr, left, right);
    /************************/

    sort(arr, left, mid - 1);
    sort(arr, mid + 1, 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
package com.kang;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {1,3,7,6,2,5,4};
        QuickSort(arr, 0, arr.length-1);
        printArr(arr);
    }

    public static void QuickSort(int[] arr, int leftBound, int rightBound) {
        if (leftBound >= rightBound) return;
        int mid = partition(arr, leftBound, rightBound);
        QuickSort(arr, leftBound, mid-1);
        QuickSort(arr, mid+1, rightBound);
    }

    public static int partition(int[] arr, int leftBound, int rightBound) {
        int temp = arr[rightBound];
        int left = leftBound;
        int right = rightBound-1;

        while (left <= right) {
            if (left <= right && arr[left] <= temp) left++;
            if (left <= right && arr[right] > temp) right--;
            if (left < right) swap(arr, left, right);
        }
        swap(arr, left, rightBound);
        return left;
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void printArr(int[] arr) {
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
    }
}
算法分析

时间复杂度:序列每次都要分成两部分进行排序，共需要要logN次，而每一行需要N次排序，所以时间复杂度为N(logN)，即O(NlogN)

空间复杂度:需要额外的空间logN，O(N)。

稳定性:不稳定

归并排序

归并排序是个二叉树的后序遍历。

算法思路及原理
  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列;
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置;
  4. 重复步骤3直到某一指针超出序列尾;
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

代码框架如下

1
2
3
4
5
6
7
8
9
10
void sort(int[] arr, int left, int right) {
    int mid = (left + right) / 2;
    sort(arr, left, mid);
    sort(arr, mid+1, right);

    /****** 后序遍历位置 ******/
    // 合并两个排好序的子数组
    merge(arr, left, mid+1, 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
package com.kang;

public class MergeSort2 {
    public static void main(String[] args) {
        int[] arr = {1,3,7,6,2,5,4};
        sort(arr, 0, arr.length-1);
//        printArr(arr);
    }


    static void sort(int[] arr, int left, int right) {
        if (left == right) return;
        int mid = left + (right-left)/2;
        sort(arr, left, mid);
        sort(arr, mid+1, right);
        merge(arr, left, mid+1, right);
    }

    static void merge(int[] arr, int left, int mid, int right) {
//        int[] temp = new int[arr.length];
        int[] temp = new int[right-left+1];

        int leftPoint = left; // 指针指向第一部分开始位置
        int rightPoint = mid; // 指针指向第二部分开始位置
        int tempPoint = 0; // 指针指向临时数组开始位置

        while (leftPoint < mid && rightPoint <= right) {
            if (arr[leftPoint] <= arr[rightPoint]) { // merge算法稳定的原因
                temp[tempPoint++] = arr[leftPoint++];
            } else {
                temp[tempPoint++] = arr[rightPoint++];
            }
        }
        while (leftPoint < mid) temp[tempPoint++] = arr[leftPoint++];
        while (rightPoint <= right) temp[tempPoint++] = arr[rightPoint++];

//        for (int i = left; i <= right; i++) {
//            arr[i] = temp[i];
//        }
        for (int i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }

//        printArr(temp);
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    static void printArr(int[] arr) {
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
    }
}
算法分析

时间复杂度序列每次都要分成两部分进行排序，共需要要logN + 1次，而每一行无论如何分，都需要N次排序，所以时间复杂度为N(logN + 1)，即O(nlogn)

空间复杂度:需要额外的空间N，O(N)。

稳定性:比较两个指针所指向的元素，选择相对小的元素放入到合并空间，但是当这两个元素相同时，选择前者放入temp序列中，保证相同元素前后关系的不变，保证了算法的稳定性。

1
2
3
4
5
if (arr[i] <= arr[j]) { // merge算法稳定的原因
    temp[k++] = arr[i++];
} else {
    temp[k++] = arr[j++];
    }

小结

199 637 515

相关题目

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List res) {
        if (root == null) return;

        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
     }

    public void inorder(TreeNode root, List res) {
        if (root == null) return;

        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

145. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    public void postorder(TreeNode root, List res) {
        if (root == null) return;

        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}

102.二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

利用队列的先入先出特点，通过迭代完成

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> resList = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        BFS(root);
        return resList;
    }

    public void BFS(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(node);
        
        while (!que.isEmpty()) {
            List<Integer> tmpList = new ArrayList<>();
            int depth = que.size();

            while (depth > 0) {
                TreeNode tmpNode = que.poll();
                tmpList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                depth--;
            }
            resList.add(tmpList);
        }
    }
}
  • 时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
  • 空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left_depth = maxDepth(root.left);
        int right_depth = maxDepth(root.right);
        return Math.max(left_depth, right_depth) + 1;
    }
}
  • 时间复杂度O(n)。需要遍历所以节点
  • 空间复杂度O(depth)。二叉树的高度
101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;

        return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
    }
}
  • 时间复杂度O(n)
  • 空间复杂度O(depth)
112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return targetSum == root.val;
        return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val);
    }
}
  • 时间复杂度O(n)
  • 空间复杂度O(depth)
199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();

        if (root == null) return res;

        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while (!que.isEmpty()) {
            int depth = que.size()-1;
            TreeNode node = que.poll();
            res.add(node.val);
            if (node.right != null) que.offer(node.right);
            if (node.left != null) que.offer(node.left);

            while (depth > 0) {
                node = que.poll();
                if (node.right != null) que.offer(node.right);
                if (node.left != null) que.offer(node.left);
                depth--;
            }
        }
        return res;
    }
}
637. 二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        // if (root == null) return res;

        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while (!que.isEmpty()) {
            double sum = 0;
            int size = que.size();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                sum += node.val;

                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            res.add(sum / size);
        }

        return res;
    }
}

515. 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();

        if (root == null) return res;
        que.offer(root);

        while (!que.isEmpty()) {
            int size = que.size();
            int max = Integer.MIN_VALUE;
            for (int i=0; i<size; i++) {
                TreeNode node = que.poll();
                if (max < node.val) max = node.val;

                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            res.add(max);
        }

        return res;
    }
}
  • 本文标题：BinaryTree
  • 本文作者：Kang
  • 创建时间：2021-12-26 22:27:18
  • 本文链接：ykhou.github.io2021/12/26/BinaryTree/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！