题解 | #在二叉树中找到两个节点的最近公共祖先#

package org.example.test;

import com.alibaba.fastjson.JSONObject;
import netscape.javascript.JSObject;

import java.util.LinkedList;


/**
 * 先分别用回溯算法遍历指定2个节点，并形成2个链表，然后遍历2个链表，直到不相同为止
 */
public class LowestCommonAncestorTest {

    private static LinkedList<LinkedList<TreeNode>> list2 = new LinkedList<>();
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        lowestCommonAncestor(treeNode1, 2, 3);
        System.out.println(JSONObject.toJSONString(list2));
    }
    public static class TreeNode {
        int val = 0;
        TreeNode right;
        TreeNode left;

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

        public int getVal() {
            return val;
        }
    }

    public static int lowestCommonAncestor(TreeNode root, int o1, int o2) {
        // write code here
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        getLinkedList(root, list, o1);
        LinkedList<TreeNode> list3 = new LinkedList<>();
        list3.add(root);
        getLinkedList(root, list3, o2);
        LinkedList<TreeNode> node1=list2.poll();
        LinkedList<TreeNode> node2=list2.poll();
        TreeNode ret = null;
        for (TreeNode node11=node1.poll(), node12=node2.poll(); node11!=null && node12!=null; node11=node1.poll(), node12=node2.poll()){
            System.out.println(node11.val +":" + node12.val );
            if (node11.val != node12.val){
                break;
            }
            ret = node11;
        }
        System.out.println(ret);
        return ret.val;
    }

    private static void  getLinkedList(TreeNode root,LinkedList<TreeNode> list, int value) {
        if (root.val==value) {
            list2.add(new LinkedList<>(list));
            return;
        }
        if (root.left != null) {
            list.add(root.left);
            getLinkedList(root.left, list, value);
            list.removeLast();
        }
        if (root.right != null) {
            list.add(root.right);
            getLinkedList(root.right, list, value);
            list.removeLast();
        }
    }
}