在二叉树中找到两个节点的最近公共祖先_

Java

pein531

可以用递归，但是我觉得那个思路有点难想，还是写了个用哈希表存储父节点的思路。首先遍历二叉树，构建好子节点指向父节点的映射，之后就可以像链表求交点一样求取最近公共祖先。先对p节点向上追溯到根，并记录下沿途的路径节点，之后q节点在往上追溯的过程中，碰到的第一个在路径节点集合中的节点就是我们要求的最近公共祖先节点。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;
 
class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 构建二叉树
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        TreeNode root = new TreeNode(Integer.parseInt(params[1]));
        HashMap<Integer, TreeNode> map = new HashMap<>();
        map.put(root.val, root);
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int val = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(val);
            if(leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if(rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        // 获得最近公共祖先
        params = br.readLine().split(" ");
        TreeNode p = map.get(Integer.parseInt(params[0])), q = map.get(Integer.parseInt(params[1]));
        System.out.println(lowestCommonAncestor(root, p, q).val);
    }
    
    private static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        HashMap<TreeNode, TreeNode> child2parent = new HashMap<>();
        child2parent.put(root, root);     // 根的父节点是自己
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left != null){
                queue.offer(node.left);
                child2parent.put(node.left, node);
            }
            if(node.right != null){
                queue.offer(node.right);
                child2parent.put(node.right, node);
            }
        }
        if(child2parent.get(p) == child2parent.get(q)) return child2parent.get(p);
        // 先记录p往上的路径
        HashSet<TreeNode> memory = new HashSet<>();
        memory.add(p);
        while(child2parent.get(p) != p){
            memory.add(child2parent.get(p));
            p = child2parent.get(p);
        }
        // 然后再从q往上找最先与路径相交的节点
        while(!memory.contains(q)) q = child2parent.get(q);
        return q;
    }
}

发表于 2021-11-14 20:05:55 回复(0)

C

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

typedef int Id;

typedef struct {
  Id id;
  Id l_child, r_child;
} TNodeInfo, *INFO;

int lowestCommonAncestor(INFO infos, Id root_id, Id p, Id q) {
  if (!root_id || root_id == p || root_id == q) return root_id;
  const int ls = lowestCommonAncestor(infos, (*(infos + root_id)).l_child, p, q);
  const int rs = lowestCommonAncestor(infos, (*(infos + root_id)).r_child, p, q);
  return ls && rs ? root_id : ls ? ls : rs;
}

int main(const int argc, const char** const argv) {
  int n, root_id;
  fscanf(stdin, "%d %d", &n, &root_id);
  
  TNodeInfo infos[n + 1];
  Id fa, l_ch, r_ch;
  while (n--) {
    fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch);
    (*(infos + fa)).id = fa;
    (*(infos + fa)).l_child = l_ch;
    (*(infos + fa)).r_child = r_ch;
  }
  
  Id o1, o2;
  fscanf(stdin, "%d %d", &o1, &o2);
  fprintf(stdout, "%d", lowestCommonAncestor(infos, root_id, o1, o2));
  return 0;
}

发表于 2021-07-31 19:29:58 回复(0)

老子的offer呢

#include <bits/stdc++.h>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* lch;
    TreeNode* rch;
    TreeNode(int x):val(x),lch(NULL),rch(NULL){}
};

void createTree(TreeNode* root, int& cnt){
    if(cnt == 0) return;
    int p, l, r;
    cin >> p >> l >> r;
    
    if(l){
        TreeNode* lch = new TreeNode(l);
        root->lch = lch;
        createTree(root->lch, --cnt);
    }
    if(r){
        TreeNode* rch = new TreeNode(r);
        root->rch = rch;
        createTree(root->rch, --cnt);
    }
    return;
}

TreeNode* findCommonNode(TreeNode* root, int v1, int v2){
    if(!root) return NULL;
    if(root->val == v1 || root->val == v2)
        return root;
    TreeNode* left = findCommonNode(root->lch, v1, v2);
    TreeNode* right = findCommonNode(root->rch, v1, v2);
    if(left && right)
        return root;
    else if(left)
        return left;
    else return right;
}

int main(){
    int n, root_val;
    cin >> n >> root_val;
    TreeNode* root = new TreeNode(root_val);
    createTree(root, n);
    int o1_val, o2_val;
    cin >> o1_val >> o2_val;
    TreeNode* node = findCommonNode(root, o1_val, o2_val);
    cout << node->val << endl;
    return 0;
}

发表于 2020-05-07 11:48:39 回复(1)

Java

秋風掃落葉

import java.util.*;

public class Main {
	static HashMap<Integer, Integer[]> hm;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] str = sc.nextLine().split(" ");
		int n = Integer.parseInt(str[0]);
		int r = Integer.parseInt(str[1]);
		
		Integer[] child;
		hm = new HashMap<>();
		for(int i = 0;i < n;i++){
			String[] str1 = sc.nextLine().split(" ");
			int fa = Integer.parseInt(str1[0]);
			int lc = Integer.parseInt(str1[1]);
			int rc = Integer.parseInt(str1[2]);
			child = new Integer[2];
			child[0] = lc;
			child[1] = rc;
			hm.put(fa, child);
		}
        
        String[] str2 = sc.nextLine().split(" ");
        int o1 = Integer.parseInt(str2[0]);
        int o2 = Integer.parseInt(str2[1]);
		
		Node root = new Node(r);
        Node node1 = new Node(o1);
        Node node2 = new Node(o2);
		buildTree(root);
        Node res = LCA(root, node1, node2);
		System.out.println(res.val);
	}
    
    // 递归查找最近公共祖先
    private static Node LCA(Node root, Node node1, Node node2){
        if(root == null){
            return null;
        }
        if(root.val == node1.val){
            return node1;
        }
        if(root.val == node2.val){
            return node2;
        }
        Node left = LCA(root.left, node1,node2);
        Node right = LCA(root.right, node1,node2);
        if(left != null && right != null){
            return root;
        }else if(left == null){
            return right;
        }else{
            return left;
        }
    }

	private static void buildTree(Node root) {
		
		if(root == null)
			return;
		
		if(hm.containsKey(root.val)){
			Node lc = null;
			Node rc =null;
			Integer[] ch = hm.get(root.val);
			if(ch[0]!= 0){
				lc = new Node(ch[0]);
				lc.parent = root;
			}
			if(ch[1]!= 0){
				rc = new Node(ch[1]);
				rc.parent = root;
			}
			root.left = lc;
			root.right = rc;
			
			buildTree(lc);
			buildTree(rc);
		}
	}
}

class Node {
    int val;
    Node parent;
    Node left;
    Node right;
    public Node(int val){
        this.val = val;
    }
}

发表于 2019-09-19 16:14:28 回复(0)

天命剑主

//
// Created by yuanhao on 2019-8-30.
//

#include <iostream>

using namespace std;

//题目描述
//给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。 
//输入描述:
//第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
//以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
//最后一行为节点 o1 和 o2。
//输出描述:
//输出一个整数表示答案。
//
//示例1
//输入
//8 1
//1 2 3
//2 4 5
//4 0 0
//5 0 0
//3 6 7
//6 0 0
//7 8 0
//8 0 0
//4 5
//输出
//2
int main() {
    int n = 0;
    int root = 0;
    cin >> n >> root;
    int father[n + 1];
    int f, l, r;
    for (int i = 0; i < n; i++) {
        cin >> f >> l >> r;
        if (l != 0) {
            father[l] = f;
        }
        if (r != 0) {
            father[r] = f;
        }
    }

    int ln = 0, rn = 0;
    cin >> ln >> rn;

    int ld = 0, rd = 0; // 节点深度
    l = ln, r = rn;
    while (l != root) {
        ld++;
        l = father[l];
    }
    while (r != root) {
        rd++;
        r = father[r];
    }
    l = ln;
    r = rn;
    if (ld > rd) {
        int bd = ld - rd;
        for (int i = 0; i < bd; i++) {
            l = father[l];
        }
    } else {
        int bd = rd - ld;
        for (int i = 0; i < bd; i++) {
            r = father[r];
        }
    }
    while (l != r) {
        l = father[l];
        r = father[r];
    }
    cout << l << endl; // 或者 cout << r << endl; 都是一样的
}

发表于 2019-08-30 10:21:29 回复(3)

Java

牛客329800565号

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;

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

public class Main {
    private static HashMap<TreeNode,TreeNode> map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 构建二叉树
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        TreeNode root = new TreeNode(Integer.parseInt(params[1]));
        HashMap<Integer, TreeNode> map = new HashMap<>();
        map.put(root.val, root);
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int val = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(val);
            if(leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if(rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        // 获得最近公共祖先
        params = br.readLine().split(" ");
        TreeNode p = map.get(Integer.parseInt(params[0])), q = map.get(Integer.parseInt(params[1]));
        System.out.println(lowestCommonAncestor(root, p, q).val);
    }


    private static void setMap(TreeNode head) {
        if(head==null)
            return;
        if(head.left!=null){
            map.put(head.left,head);
        }
        if(head.right!=null)
        {
            map.put(head.right,head);
        }
        setMap(head.left);
        setMap(head.right);
    }

    private static TreeNode lowestCommonAncestor(TreeNode head, TreeNode o1, TreeNode o2) {
        if(head==null) return head;
        map=new HashMap<TreeNode,TreeNode>();
        if(head!=null) {
            map.put(head,null);
        }
        setMap(head);
        HashSet<TreeNode> path=new HashSet<>();
        while(map.containsKey(o1)){
            path.add(o1);
            o1=map.get(o1);
        }
        while(!path.contains(o2)){
           o2=map.get(o2);
        }
        return o2;

    }


}

发表于 2022-04-15 18:55:48 回复(0)

Python3

毓毓子最可爱

#节点数，根节点
n,root=map(int,input().split())
#树和C1的祖先数组
f,v=[0]*(n+1),[1]*(n+1)
#建立树
for _ in range(n):
    fa,lch,rch=map(int,input().split())
    f[lch]=f[rch]=fa
c1,c2=map(int,input().split())
#寻找c1的所有祖先
while c1!=root:
    v[c1],c1=0,f[c1]
#第一个没被标记的祖先就是最近公共祖先
while c2!=root and v[c2]:
    c2=f[c2]
print(c2)

发表于 2021-08-06 09:04:36 回复(0)

Python

歪比歪比阿嘛鸿

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p:int, q:int) -> 'TreeNode':
        if not root&nbs***bsp;root.val == p&nbs***bsp;root.val == q:return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        if left:return left
        if right:return right
 

if __name__ == '__main__':
    n, root_val = map(int, input().split())
    node_key = {}
    lst = []
    for i in range(n):
        v, l, r = map(int, input().split())
        lst.append((v ,l, r))
        node_key[v] = TreeNode(v)
        if i == 0:root = node_key[v]
    for v, l, r in lst:
        if l:
            node_key[v].left = node_key[l]
        if r:
            node_key[v].right = node_key[r]
    p, q = map(int, input().split())
    node = Solution().lowestCommonAncestor(root, p, q)
    print(node.val)

发表于 2021-08-02 19:48:34 回复(0)

科大15届软工代言人

import java.util.Scanner;
import java.util.HashMap;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int sum = in.nextInt();
        int val = in.nextInt();
        HashMap<Integer,Node> map = new HashMap<Integer,Node>();
        if(sum > 0) {
            int[][] arr = new int[sum][3];
            for(int i = 0; i<sum; i++) {
                for(int j = 0; j<3; j++){
                    arr[i][j] = in.nextInt();
                }
                map.put(arr[i][0],new Node(arr[i][0]));
            }
            for(int i = 0; i<sum; i++) {
                if(arr[i][1] != 0)
                    map.get(arr[i][0]).setLeftChild(map.get(arr[i][1]));
                if(arr[i][2] != 0)
                    map.get(arr[i][0]).setRightChild(map.get(arr[i][2]));
            }
            int v1 = in.nextInt();
            int v2 = in.nextInt();
            Node root = map.get(val);
            Node child1 = map.get(v1);
            Node child2 = map.get(v2);
            System.out.println(new Main().latestCommonAncestor(root,child1,child2).getValue());
         }
     }
    
      public Node latestCommonAncestor(Node head, Node child1, Node child2) {
         if(head == null || head == child1 || head == child2) {
               return head;
          }
          Node left = latestCommonAncestor(head.getLeftChild(),child1,child2);
          Node right = latestCommonAncestor(head.getRightChild(),child1,child2);
          if(left != null && right != null) {
              return head;
          }
          return left!=null? left: right;
      }
}

class Node {
    private Node leftC;
    private Node rightC;
    private int value;
    
    Node(int value) {
        this.value = value;
    }
    
    public void setLeftChild(Node leftC) {
        this.leftC = leftC;
    }
    public void setRightChild(Node rightC) {
        this.rightC = rightC;
    }
    
    public Node getLeftChild() {
        return this.leftC;
    }
    public Node getRightChild() {
        return this.rightC;
    }
    public int getValue() {
        return this.value;
    }
}
运行时间：2253ms 占用内存：241908KB  .代码已通过，仅供参考。

编辑于 2021-05-22 22:05:35 回复(0)

柠檬茶c

import java.util.Scanner;

/**
 * 比较Low的写法，用了boolean数组进行标记
 */
public class Main {

    public static class Node {
        public int id;
        public int parent;
        public int left;
        public int right;

        public Node(int id, int left, int right) {
            this.id = id;
            this.left = left;
            this.right = right;
        }
    }


    public static void preOrder(Node[] nodes, int id, int parent) {
        if (id != 0) {
            nodes[id].parent = parent;
            preOrder(nodes, nodes[id].left, id);
            preOrder(nodes, nodes[id].right, id);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int root = in.nextInt();
        Node[] nodes = new Node[n+1];
        boolean[] visited = new boolean[n+1];
        for (int i = 0; i < n; i++) {
            int p = in.nextInt();
            int left = in.nextInt();
            int right = in.nextInt();
            nodes[p] = new Node(p, left, right);
        }
        preOrder(nodes, root, 0);
        int o1 = in.nextInt(), o2 = in.nextInt();
        while (o1 != 0) {
            visited[o1] = true;
            o1 = nodes[o1].parent;
        }
        while (o2 != 0) {
            if (visited[o2]) {
                System.out.print(o2);
                break;
            } else {
                o2 = nodes[o2].parent;
            }
        }
    }
}

发表于 2020-08-01 22:23:24 回复(0)

SteDylan

#include <cstdio>
(802)#include <queue>

using namespace std;

int main()
{
    int n, root;
    priority_queue<int, vector<int>, greater<int>> queue;
    int dis[n];
    scanf("%d %d", &n, &root);
    int tree[n]; // 使用一维数组保存二叉树，数组的值为对应下标的父节点
    for (int i = 1; i <= n; i++)
    {
        int left, right, father;
        scanf("%d %d %d", &father, &left, &right);
        if (left != 0)
        {
            tree[left] = father;
        }
        if (right != 0)
        {
            tree[right] = father;
        }
    }
    tree[root] = -1;
    int firstNode, secondNode;
    scanf("%d %d", &firstNode, &secondNode);
    int firstCount = -1;        // 第一个结点到公共结点的距离
    int secondCount = 0;        // 第二个结点到公共结点的距离
    int firstFatherNodes[n]; // 保存第一个结点的父节点，包括自己
    while (firstNode != -1)
    {
        firstCount++;
        firstFatherNodes[firstCount] = firstNode;
        firstNode = tree[firstNode];
    }
    int secondCurrent = secondNode;
    for (int i = 0; i <= firstCount; i++) // 计算第二个结点到第一个结点的父结点的距离
    {
        secondCount = 0;
        secondCurrent = secondNode;
        while (secondCurrent != firstFatherNodes[i] && secondCurrent != -1)
        {
            secondCount++;
            secondCurrent = tree[secondCurrent];
        }
        if (secondCurrent == -1)
        {
            continue;
        }
        printf("%d",firstFatherNodes[i]);
        break;
    }
    return 0;
}

发表于 2020-03-09 13:20:44 回复(0)

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
int LCA(int root,int* lc,int* rc,int a,int b)
{
    if(!root || root==a || root==b)
        return root;
    int l = LCA(lc[root],lc,rc,a,b);
    int r = LCA(rc[root],lc,rc,a,b);
    if(!l && !r) return 0;
    if(l && r) return root;
    return (l ? l : r);
}
int main()
{
    int n,root;
    cin>>n>>root;
    int p;
    int* lc = new int[n+1];
    int* rc = new int[n+1];
    for(int i=0;i<n;++i)
    {
        cin>>p;
        cin>>lc[p]>>rc[p];
    }
    int a,b;
    cin>>a>>b;
    cout<<LCA(root,lc,rc,a,b);

    return 0;
}

发表于 2020-02-06 21:42:24 回复(0)

喜欢吃火锅的哈里

// father数组+栈 解决
#include <stdio.h>
#include <algorithm>
#include <stack>
#include <cstring>
using namespace std;
//int matrix[2001][2001];
int f[500001];
int main()
{
    int n, rt;
    scanf("%d %d", &n, &rt);

    int fa, lch, rch;
    memset(f, 0, sizeof(f));
    int cnt = n;
    while(cnt--) {
        scanf("%d %d %d", &fa, &lch, &rch);
        if(lch != 0)
            f[lch] = fa;
        if(rch != 0)
            f[rch] = fa;
    }
    int o1, o2;
    scanf("%d %d", &o1, &o2);
    stack<int>os1;
    stack<int>os2;
    os1.push(o1);
    os2.push(o2);
    while(f[o1] != 0) {
        os1.push(f[o1]);
        o1 = f[o1];
    }
    while(f[o2] != 0 ) {
        os2.push(f[o2]);
        o2 = f[o2];
    }
    int ans;
    int top = os1.top();
    while(!os1.empty() && !os2.empty() && top == os2.top()) {
        ans = top;
        os1.pop();
        os2.pop();
        top = os1.top();
    }
    printf("%d\n", ans);
    return 0;
}

发表于 2019-10-30 11:13:23 回复(0)

yhh2021

/*

输入的时候记录每个节点的父节点；

再记录从第一个节点到根节点所经过的节点，

最后遍历第二个节点到最近公共节点的路径。

*/

#include<iostream>

#include<vector>
using namespace std;
void fun_nearestA()
{
int n, root;
scanf("%d%d",&n,&root);
vector<int> pNode(n + 1, -1);
vector<int> recard(n+1,-1);
for (int i = 0; i < n; ++i)
{
int temp1, temp2, temp3;
scanf("%d%d%d",&temp1,&temp2,&temp3);
pNode[temp2] = temp1;
pNode[temp3] = temp1;
}
int node1, node2;
scanf("%d%d",&node1,&node2);
while (node1 != -1)
{
recard[node1] = 1;
node1 = pNode[node1];
}
while (node2 != -1 && recard[node2] == -1)
node2 = pNode[node2];
printf("%d\n",node2);
}
int main()
{
fun_nearestA();
return 0;
}

编辑于 2019-10-25 14:56:27 回复(0)

Trashw

#include <iostream>
#include <map>
using namespace std;
map<int, pair<int, int>>in;
int a, b;

int getparent(int root) {
	if (root == a || root == b) {
		return root;
	}
	if (root == 0)
		return 0;
	int l = getparent(in[root].first);
	int r = getparent(in[root].second);
	if (l!=0&&r!=0) {
		return root;
	}
	return l!=0?l:r;
}


int main() {
	int m, ro;
	cin >> m >> ro;

	int root, left, right;
	for (int i = 0; i<m; ++i) {
		cin >> root >> left >> right;
		in[root] = { left,right };
	}
	cin >> a>>b;
	cout<<getparent(ro);
}

发表于 2019-09-09 20:50:07 回复(0)

Disconnect

import java.util.*;
public class Main{
    static HashMap<Integer,Integer[]> hm;
    static TreeNode rt,o1,o2;
    public static void main(String[] args)
    {
        int n,root;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        root = sc.nextInt();
        hm = new HashMap<Integer,Integer[]>();
        Integer[] t;
        int val;
        for(int i=0;i<n;i++)
        {
            t = new Integer[2];
            val = sc.nextInt();
            t[0] = sc.nextInt();
            t[1] = sc.nextInt();
            hm.put(val,t);
        }
        rt = new TreeNode(root);
        buildTree(rt);                          //循环构建二叉树
        getTreeNodeO1(rt,sc.nextInt());         //前序遍历找到该节点
        getTreeNodeO2(rt,sc.nextInt());         //前序遍历找到该节点
        //printTree(rt);
        ArrayList<Integer> al1 = findRtPath(o1);   //获得该节点对应的路径
        ArrayList<Integer> al2 = findRtPath(o2);   //获得该节点对应的路径
        ArrayList<Integer[]> commonlst = new ArrayList<Integer[]>();
        Integer[] tmp;
        Integer temp;
        for(int i=0;i<al1.size();i++){
            temp = al1.get(i);
            if(al2.contains(temp))
            {
                tmp = new Integer[2];
                tmp[0] = temp;
                tmp[1] = i + al2.indexOf(tmp);   //路径距离和
                commonlst.add(tmp);
                al2.remove(temp);
            }
        }
        for(int i=0;i<al2.size();i++){
            temp = al2.get(i);
            if(al1.contains(temp))
            {
                tmp = new Integer[2];
                tmp[0] = temp;
                tmp[1] = i + al1.indexOf(tmp);   //路径距离和
                commonlst.add(tmp);
            }
        }
        Integer near = Integer.MAX_VALUE;    //最短路径
        Integer res = -1;                    //结果
        for(int i=0;i<commonlst.size();i++)
        {
            tmp = commonlst.get(i);
            if(tmp[1]<near)
            {
                res = tmp[0];
                near = tmp[1];
            }
        }
        System.out.println(res);
    }
    private static ArrayList<Integer> findRtPath(TreeNode n){
        ArrayList<Integer> al = new ArrayList<Integer>();
        while(n!=null)
        {
            al.add(n.getVal());
            n = n.father;
        }
        return al;
    }
    private static void getTreeNodeO2(TreeNode rt,int n){
        assert n>0;
        if(rt==null)
        {
        	return;
        }
        if(rt.getVal()==n)
        {
            o2 = rt;
            return;
        }
        else{
            getTreeNodeO2(rt.left,n);
            getTreeNodeO2(rt.right,n);
        }
    }
    private static void getTreeNodeO1(TreeNode rt,int n){
        assert n>0;
        if(rt==null)
        {
        	return;
        }
        if(rt.getVal()==n)
        {
            o1 = rt;
            return;
        }
        else{
            getTreeNodeO1(rt.left,n);
            getTreeNodeO1(rt.right,n);
        }
    }
    private static void printTree(TreeNode rt){
    	if(rt!=null){
    		if(rt.getVal()!=0){
    			System.out.print(rt.getVal());
        	    printTree(rt.left);
        	    printTree(rt.right);
    		}

    	}
    }
    private static void buildTree(TreeNode rt)
    {
        Integer[] t;
        if(rt!=null && hm.containsKey(rt.getVal()))
        {
            t = hm.get(rt.getVal());
            TreeNode left,right;
            left = null;
            right = null;
            if(t[0]!=0){
            	left = new TreeNode(t[0]);
                left.father = rt;
            }
            if(t[1]!=0)
            {
            	right = new TreeNode(t[1]);
                right.father = rt;
            }   
            rt.left = left;
            rt.right = right;
            buildTree(left);
            buildTree(right);
        }
    }
}

class TreeNode{
    private int val;
    public TreeNode left,right,father;
    public void setVal(int n){
        this.val = n;
    }
    public int getVal(){
        return this.val;
    }
    public TreeNode(int n)
    {
        this.val = n;
        left = null;
        right = null;
        father = null;
    }
}

发表于 2019-09-02 16:02:10 回复(0)

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

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题