[数据结构与算法]输入一个数组构建一颗二叉树，并且找出二叉树两个节点的最近公共祖先

package org.example;/**
 * Copyright (C), 2019-2021
 * author  candy_chen
 * date   2021/8/8 19:05
 *
 * @Classname test
 * Description: 测试
 */

import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *
 */


public class Foo{

    class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    /**
     * 指定节点位头结点构建二叉树
     * @param array
     * @param index
     * @return
     */
    private TreeNode createBinaryTreeByArray(int[] array, int index) {
        TreeNode tn = null;
        if (index<array.length) {
            int value = array[index];
            tn = new TreeNode(value);
            tn.left = createBinaryTreeByArray(array, 2*index+1);
            tn.right = createBinaryTreeByArray(array, 2*index+2);
            return tn;
        }
        return tn;
    }
    TreeNode root;
    public TreeNode BinaryTree(int[] array) {
        return root = createBinaryTreeByArray(array, 0);
    }

    /**
     * 数组的中点构建二叉树
     * @param array
     * @return
     */
    public TreeNode arraybuildTree(int[] array) {
        if (array.length == 0) {
            return null;
        }
        TreeNode root = buildTree(array, 0, array.length-1);
        return root;
    }
    private TreeNode buildTree(int[] array, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(array[mid]);
        root.left = buildTree(array, start, mid-1);
        root.right = buildTree(array, mid + 1, end);
        return root;
    }

    /**
     * 二叉树的最近公共祖先
     * 非递归实现
     */
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.value, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.value, root);
            dfs(root.right);
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            visited.add(p.value);
            p = parent.get(p.value);
        }
        while (q != null) {
            if (visited.contains(q.value)) {
                return q;
            }
            q = parent.get(q.value);
        }
        return null;
    }

    //测试
    @Test
    public void test() {
        TreeNode root = arraybuildTree(new int[]{1, 2, 3, 4, 5, 6, 7});
        TreeNode treeNode = lowestCommonAncestor(root, new TreeNode(3), new TreeNode(7));
        System.out.println(treeNode.value);
    }


}