数据结构-二叉树纲领篇

理解前、中、后序遍历

前序遍历A-B-D-F-G-H-I-E-C

中序遍历F-D-H-G-I-B-E-A-C

后序遍历F-H-I-G-D-E-B-C-A

前序(左右根)，中序(左右根)，后序(左右根)

快速排序(思想:前序遍历)

先构建分界点(理解为根)，然后去左右子数组构建分界点(构建左右叶节点)

package com.2023年，algorithm.basis;import java.util.Arrays;public class QuickSort {    public static void main(String[] args) {        int[] arr = {5, 3, 8, 4, 2, 7, 1, 10};        quickSort(arr, 0, 6);        System.out.println(Arrays.toString(arr));    }    public static void quickSort(int[] arr, int left, int right) {        if (left < right) {            int pivotIndex = partition(arr, left, right);            quickSort(arr, left, pivotIndex - 1);            quickSort(arr, pivotIndex + 1, right);        }    }    private static int partition(int[] arr, int left, int right) {        int pivot = arr[right];        int i = left;        for (int j = left; j < right; j++) {            if (arr[j] < pivot) {                swap(arr, i, j);                i++;            }        }        swap(arr, i, right);        return i;    }    private static void swap(int[] arr, int i, int j) {        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }}

归并排序(思想:后序遍历)

这种后序遍历的想法体现在并购排序的代码实现中。我们首先使用递归算法分别对左部分子序列和右部分子序列进行排序，然后将排序好的两个子序列合并成更大的有序列。这种合并过程与合并两棵二叉树的过程非常相似，也就是说，它是树形结构的后序遍历。

首先，将数组逐层拆分，直到每个子数组的大小为1。

然后从底层逐层向上合并。

参考具体流程 https://blog.csdn.net/STILLxjy/article/details/108855222

package com.2023年，algorithm.basis;/** * 归并排序 */public class MergeSort {    private static void mergeSort(int[] arr, int left, int right) {        if (left >= right) {            return;        }        int mid = (left + right) / 2;        mergeSort(arr, left, right);        mergeSort(arr, mid + 1, right);        merge(arr, left, mid, right);    }    private static void merge(int[] arr, int left, int mid, int right) {        int[] tempArr = new int[right - left + 1];        int i = left, j = mid + 1, k = 0;        //比较左右两个数组，找出小的，放在临时数组中        while (i <= mid && j <= right) {            if (arr[i] <= arr[j]) {                tempArr[k++] = arr[i++];            } else {                tempArr[k++] = arr[j++];            }        }        ///左右两侧数组多元素加临时数组        while (i <= mid) {            tempArr[k++] = arr[i++];        }        while (j <= right) {            tempArr[k++] = arr[j++];        }        for (int m = 0; m < tempArr.length; m++) {            arr[left + m] = tempArr[m];        }    }}

深入了解前、中、后序遍历数组和链表框架

/* 迭代遍历数组 */void traverse(int[] arr) {    for (int i = 0; i < arr.length; i++) {    }}/* 递归遍历数组 */void traverse(int[] arr, int i) {    if (i == arr.length) {        return;    }    // 前序位置    traverse(arr, i + 1);    // 后序位置}/* 迭代遍历单链表 */void traverse(ListNode head) {    for (ListNode p = head; p != null; p = p.next) {    }}/* 递归遍历单链表 */void traverse(ListNode head) {    if (head == null) {        return;    }    // 前序位置    traverse(head.next);    // 后序位置}

最大深度的二叉树

参考： https://leetcode.cn/problems/maximum-depth-of-binary-tree/

方法一:遍历(回溯思想)

// 记录最大深度    static int res = 0;    // 记录节点的深度    static int depth = 0;    // 主函数    static int maxDepth2(TreeNode root) {        traverse(root);        return res;    }    // 二叉树遍历框架    static void traverse(TreeNode root) {        if (root == null) {            return;        }        // 前序位置        depth++;        if (root.left == null && root.right == null) {            // 到达叶节点，更新最大深度            res = Math.max(res, depth);        }        traverse(root.left);        traverse(root.right);        // 后序位置        depth--;    }

算法最大的技巧是规律学相当于数学公式的直接应用，比如在后序位置——主要是一个节点会在遍历后上升，递归是不断在二叉树上游走的指针。

方法二:分解问题(动态规划思路)

/**     * 最大限度地分解问题     */    // 定义：输入根节点，回到这棵二叉树的最大深度    static int maxDepth(TreeNode root) {        if (root == null) {            return 0;        }        // 利用定义，计算左右子树的最大深度        int leftMax = maxDepth(root.left);        int rightMax = maxDepth(root.right);        // 整棵树的最大深度等于左右子树的最大深度，        // 然后添加根节点自己        int res = Math.max(leftMax, rightMax) + 1;        return res;    }

递归(回溯)前、中、后序遍历

List<Integer> res = new LinkedList<>();// 返回前序遍历结果Listt<Integer> preorderTraverse(TreeNode root) {    traverse(root);    return res;}// 二叉树遍历函数void traverse(TreeNode root) {    if (root == null) {        return;    }    // 前序位置    res.add(root.val);    traverse(root.left);    traverse(root.right);}

分解(动态规划)

// 定义：输入二叉树的根节点，回到这棵树的前序遍历结果Listt<Integer> preorderTraverse(TreeNode root) {    List<Integer> res = new LinkedList<>();    if (root == null) {        return res;    }    // 前序遍历的结果，root.val 在第一个    res.add(root.val);    // 使用函数定义，然后是左子树的前序遍历结果    res.addAll(preorderTraverse(root.left));    // 使用函数定义，最后，右子树的序列经历了结果    res.addAll(preorderTraverse(root.right));    return res;}

定义:如果将根节点视为第一个 1 如何打印每个节点所在的层数？

// 定义:如果将根节点视为第一个 1 如何打印每个节点所在的层数？    static void traverse2(TreeNode root,int level){        if (root == null) {            return;        }        //前序位置        System.out.println(String.format("节点 %s 在第 %d 层", root.value, level));        traverse2(root.left,level+1);        traverse2(root.right,level+1);//        System.out.println(String.format("节点 %s 在第 %d 层", root.value, level));    }

定义:输入二叉树，返回二叉树节点总数

// 定义：输入二叉树，回到这棵二叉树的节点总数    static int count(TreeNode root) {        if (root == null) {            return 0;        }        int leftCount = count(root.left);        int rightCount = count(root.right);        // 后序位置        System.out.println(String.format("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",                root.value, leftCount, rightCount));        return leftCount + rightCount + 1;    }