算法-二叉树两个叶节点最大距离

迈不过友情╰ 2023-10-08 09:03 3阅读 0赞

## 1. 二叉树中两个子节点相距最大距离 ##

获取二叉树中两个子节点相距最大距离，其实可转换为求二叉树两子树高度之和最大的问题

/**
         * Note:根节点两子树高度之和并不一定等于两个子节点相距最大距离,存在相距最远的两子节点在根节点同一子树下的情况,
         * 故需变量 max 记录出现过的值中的最大值
         *  a                                               a
         * / \                                             / \
         * b  c (根节点两子树高度之和 = 子节点相距最大距离)     b   c
         *                                               / \
         *                                              d   e
         *                                              /    \
         *                                             f     g (根节点两子树高度之和 < 子节点相距最大距离)
         *                                            /       \
         *                                           h        j
         **/

## 2. 解法 ##

递归获取二叉树左右子树的树高，取左右子树高度之和的最大值，使用一个全局变量来记录

/**
         * @return MAX_DISTANCE 全局变量记录的最大距离
         */
        public int maxDistanceOfBinaryTree(TreeNode root) {
        
            getHeight(root);
            return MAX_DISTANCE;
        }
        
        static int MAX_DISTANCE = 0;// 全局变量记录最大距离
        //获取树高
        private static int getHeight(TreeNode root) {
        
            if (root == null) return 0;
            int left = getHeight(root.left);
            int right = getHeight(root.right);
            MAX_DISTANCE = Math.max(MAX_DISTANCE, left + right); 
            return (left > right) ? left + 1 : right + 1;
        }