树专题 2016-08-19

[wolfogre]

310 Minimum Height Trees

236 Lowest Common Ancestor of a Binary Tree

[SnackMen]

/*
*[AC]236 Lowest Common Ancestor of a Binary Tree
*尝过爆栈之后的解决方法
*/
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==p || root==q)
            return root;
        List<TreeNode> stackP = new ArrayList<TreeNode>();
        List<TreeNode> stackQ = new ArrayList<TreeNode>();
        int i=0;
        if(!pathToNode(stackP,p,root) || !pathToNode(stackQ,q,root))
            return null;
        while(i<stackQ.size() && i<stackP.size()){
            if(stackP.get(i).val==stackQ.get(i).val)
                i++;
            else
                break;
        }
        return stackQ.get(i-1);
    }

    public boolean pathToNode(List<TreeNode> path ,TreeNode n,TreeNode root){
        if(root==null)
            return false;
        path.add(root);
        if(root==n)
            return true;
        if(pathToNode(path,n,root.left))
            return true;
        if(pathToNode(path,n,root.right))
            return true;
        path.remove(path.size()-1);
        return false;
    }
}

[zhaokuohaha]

310 - C# - 想到了思路, 但是写不出代码,大神的代码如下,

public class Solution
{
    int n;
    List<int>[] e; //保存边信息. e[x]=y表示从x->y有一条边
    public IList<int> FindMinHeightTrees(int n, int[,] edges)
    {
        if (n <= 0) return new List<int>();
        this.n = n;
        e = new List<int>[n];

        for (int i = 0; i < n; i++)
            e[i] = new List<int>();
        for(int i=0; i<edges.GetLength(0); i++)
        {
            int a = edges[i, 0];
            int b = edges[i, 1];
            e[a].Add(b);
            e[b].Add(a);
        }

        int[] d1 = new int[n];//记录第一轮遍历最长路径
        int[] d2 = new int[n];//记录第二轮遍历最长路径
        int[] pre = new int[n];

        bfs(0, d1, pre);
        int u = 0;
        for(int i=0; i<n; i++)
            if (d1[i] > d1[u]) u = i;

        bfs(u, d2, pre);
        int v = 0;
        for (int i = 0; i < n; i++)
            if (d2[i] > d2[v]) v = i;

        List<int> list = new List<int>();
        while(v != -1)
        {
            list.Add(v);
            v = pre[v];
        }
        List<int> res = new List<int>();
        res.Add(list[(list.Count-1) / 2]);
        if (list.Count % 2 == 0)
            res.Add(list[list.Count / 2]);
        return res;
    }

    private void bfs(int start, int[] dist, int[] pre)
    {
        bool[] visited = new bool[n];
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(start);
        dist[start] = 0;
        visited[start] = true;
        pre[start] = -1;

        while (queue.Count > 0)
        {
            int u = queue.Dequeue();
            foreach(var v in e[u])
            {
                if (!visited[v])
                {
                    visited[v] = true;
                    dist[v] = dist[u] + 1;
                    queue.Enqueue(v);
                    pre[v] = u;
                }
            }
        }
    }
}

[zhaokuohaha]

236 - C# - 从根节点开始比直到不一样

public class Solution
{
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        Stack<TreeNode> pl = new Stack<TreeNode>();
        Stack<TreeNode> ql = new Stack<TreeNode>();

        dfs(root, p, pl);
        dfs(root, q, ql);

        TreeNode res = root;
        while(pl.Count>0 && ql.Count > 0)
        {
            if(pl.Peek() == ql.Peek())
            {
                res = pl.Pop(); ;
                ql.Pop();
            }
            else
            {
                return res;
            }
        }
        return res;
    }

    public bool dfs(TreeNode root, TreeNode key, Stack<TreeNode> list)
    {
        if (root == key)
        {
            list.Push(root);
            return true;
        }
        if(root.left != null && dfs(root.left, key, list))
        {
            list.Push(root);
            return true;
        }
        if(root.right != null &&dfs(root.right, key, list))
        {
            list.Push(root);
            return true;
        }
        return false;
    }
}