算法-二叉树-最大距离

2022-5-6 diaba 算法 

package com.jiucaiyuan.net.algrithm.tree;

/**
 * 树形dp套路
 * <p>
 * 树形dp套路使用前提：
 * 如果题目求解目标是S规则，则求解流程可以定成每一个节点为头节点的子树
 * 在S规则下的每个答案，并且最终答案一定在其中
 * <p>
 * 案例题
 * 【题目】二叉树节点间的最大距离
 * 从二叉树的节点a出发，可以向上或者向下走，但是沿途节点只能经过一次，
 * 到达节点b时路径上节点的个数叫做a到b的距离，那么二叉树任意两个节点
 * 之间都有距离，求整棵树上的最大距离
 * 【思路】
 * 划分为三种情况：
 * 1.头结点参与，最大可能是左树高+1+右树高
 * 2.头结点不参与，左树最大距离
 * 3.头结点不参与，右树最大距离
 * 从三种中选择最大值，就是整棵树的最大距离
 *
 * @Author jiucaiyuan  2022/5/6 23:06
 * @mail services@jiucaiyuan.net
 */

public class MaxDistanceInTree {
    public static class Info {
        public int maxDistance;
        public int height;

        public Info(int dis, int h) {
            this.maxDistance = dis;
            this.height = h;
        }
    }

    /**
     * 取得以head为头结点的整棵树最大距离
     *
     * @param head 树的头结点
     * @return head树的最大距离
     */
    public static int maxDistance(Node head) {
        return process(head).maxDistance;
    }

    /**
     * 返回以head为头结点的整棵树的信息
     *
     * @param head
     * @return
     */
    private static Info process(Node head) {
        if (head == null) {
            return new Info(0, 0);
        }
        //向左子树要信息
        Info left = process(head.left);
        //向右子树要信息
        Info right = process(head.right);
        //最大距离根据头结点是否参与分成三种情况，三种情况最大值，是本结点的最大距离
        int dis = Math.max(Math.max(left.maxDistance, right.maxDistance), left.height + 1 + right.height);
        //树的高度是左子树和右子树较大的+1
        int h = Math.max(left.height, right.height) + 1;
        return new Info(dis, h);
    }
}

« 算法-多叉树-组织party最大快乐值 | 算法-滑动窗口（滑动窗口中的最大值）»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022