Java教程

算法—二叉树

本文主要是介绍算法—二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

写树相关的算法,先搞清楚当前root节点该做什么,以及什么时候做,然后根据函数定义递归调用子节点,递归调用会让孩子节点做相同的事情。

二叉树遍历框架

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

快速排序和归并排序

​ 快速排序的逻辑:若要对 nums[lo..hi] 进行排序,先找一个分界点 p,通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p],且 nums[p+1..hi] 都大于 nums[p],然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点,最后整个数组被排序。

​ 代码:

void sort(int[] nums, int lo, int hi) {
    /****** 前序遍历位置 ******/
    // 通过交换元素构建分界点 p
    int p = partition(nums, lo, hi);
    /************************/

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

​ 从上面的代码和逻辑来看,快速排序的整个过程类似于二叉树的前序遍历。

​ 归并排序的逻辑:若要对 nums[lo..hi] 进行排序,先对 nums[lo..mid] 排序,再对 nums[mid+1..hi] 排序,最后把这两个有序的子数组合并,整个数组排好序。

​ 代码:

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);

    /****** 后序遍历位置 ******/
    // 合并两个排好序的子数组
    merge(nums, lo, mid, hi);
    /************************/
}

​ 从上面的代码和逻辑来看,归并排序的整个过程类似二叉树的后序遍历。

​ 关于树的相关算法

​ 1、搞清楚当前root节点该做什么以及什么时候做

​ 2、根据函数定义递归调用子节点,递归调用会让子节点做相同的事情。

算法实践

翻转二叉树 leetcode226

题目

输入一个二叉树根节点root,然后把整棵树镜像翻转,比如输入的二叉树如下:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

镜像翻转后,变成了:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

分析

我们只要把二叉树上的每一个节点的左右子节点进行交换,最后就是完全翻转之后的二叉树。

代码

public TreeNode invertTree(TreeNode root) {
        if (root == null){
            return null;
        }
        
        //root节点交换左右子节点(把交换的位置放在了前序遍历的位置)
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        
        //root节点的左右子节点递归地翻转它们各自的左右子节点
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

填充二叉树节点的右侧指针(leetcode 116)

题目

给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

示例

img

输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。

分析

从题目理解,可以套用上面的二叉树框架,因为都是用root节点的左节点指向右节点,按照这种思路可以写入如下的代码:

public Node connect1(Node root) {
        if(root == null){
            return null;
        }
        /*但是这里会导致,一个节点的右子节点和另一个节点的
          左子节点相连的情况无法实现。
         */
        root.left.next = root.right;

        connect1(root.left);
        connect1(root.right);

        return root;
    }

但是可以看到,这里只能将同一个节点下的左右子节点相连接(4,5),对于不同父节点的右节点和左节点(比如5,6)就无法实现。

对于这种,我们可以增加函数参数,一个节点无法实现,我们可以给函数参数为两个节点,就转化为了将每两个相邻的节点链接起来。

代码

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};

class Solution {
    public Node connect(Node root) {
        if(root == null ){
            return null;
        }
        connectTwoNode(root.left,root.right);
        return root;
    }
    public void connectTwoNode(Node node1,Node node2){
        if(node1 == null || node2 == null){
            return;
        }
        node1.next = node2;
        connectTwoNode(node1.left,node1.right);
        connectTwoNode(node2.left,node2.right);
        connectTwoNode(node1.right,node2.left);
    }
}

构造最大的二叉树(leetcode 654)

题目

给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下:

二叉树的根是数组 nums 中的最大元素。

左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。

右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

返回有给定数组 nums 构建的 最大二叉树 。

示例

输入:nums = [3,2,1,6,0,5]
输出:[6,3,5,null,2,0,null,null,1]
解释:递归调用如下所示:
- [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。
        - 空数组,无子节点。
        - [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。
            - 空数组,无子节点。
            - 只有一个元素,所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。
        - 只有一个元素,所以子节点是一个值为 0 的节点。
        - 空数组,无子节点。

分析

从题目中可知,需要使用递归方法创建一棵最大二叉树。

1、根是数组的最大元素,那么需要从数组中找到最大元素,并把它放到根的位置。

2、对最大元素的左边和右边部分,分别再寻址最大元素,并且将最大元素放到相应的位置。

3、由于需要从数组中找到最大元素,因此需要在递归函数中添加两个参数,用来寻找最大元素以及确定数组的范围。

代码

/**
 * 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 TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    public TreeNode build(int[] nums, int lo,int lw){
        if(lo > lw){
            return null;
        }
        int index = lo;
        for(int i = lo; i <= lw; i++){
            if(nums[i] > nums[index]){
                index = i;
            }
        }

        TreeNode root = new TreeNode(nums[index]);
        root.left = build(nums, lo, index - 1);
        root.right = build(nums, index + 1, lw);
        return root;
    }
}

如何判断使用前序还是中序还是后序遍历?

寻找重复的子树

题目

给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
下面是两个重复的子树:

      2
     /
    4
和

    4

分析

第一步:思考对于某一个节点,它应该做什么?

​ 对于节点2来说,需要知道以自己为根的子树是否重复,是够应该被加入到结果列表中。

第二步:要想知道以自己为根的子树是否重复,需要知道两点:

​ 1、以自己为根的子树是什么样子的

​ 对这个问题,需要使用后序遍历,因为得先知道自己的左右子树是什么样子,然后加上自己,就构成了一个完整的子树了。

​ 2、以其他节点为根的子树是什么样子的

第三步:明确了需要使用后序遍历后,可以通过拼接字符串的方式将二叉树序列化,如下代码:

String traverse(TreeNode root){
    //对空节点,可以用一个特殊字符表示
    if(root == null){
        return "#";
    }
    
    //将左右子树序列化成字符串
    String left = traverse(root.left);
    String right = traverse(root.right);
    
    //后序遍历代码位置
    //将左右子树加上自己,构成一个以自己为根的二叉树
    String subTree = left + "," +  right + "," + root.val;
    return subTree;
}

从上面的代码可以知道,用拼接的方式将二叉树序列化了。

第四步:怎么知道以别的节点为根的子树是什么样子?

​ 这里借助一个外部数据结构HashMap,来记录子树,同时记录子树出现的次数,这样就可以知道是否有重复了。

代码

class Solution {
    HashMap<String, Integer> ans = new HashMap<>();
    LinkedList<TreeNode> res = new LinkedList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return res;
    }

    public String traverse(TreeNode root){
        if(root == null){
            return "#";
        }

        String left = traverse(root.left);
        String right = traverse(root.right);

        String subStr = left + "," + right + "," + root.val;

        int feq = ans.getOrDefault(subStr,0);
        if(feq == 1){
            res.add(root);
        }

        ans.put(subStr, feq + 1);
        return subStr;
    }
}

这里用到了hashmap数据结构,HashMap是一个经常会用到的数据结构。

这篇关于算法—二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!