代码随想录算法训练营第二十天|236. 二叉树的最近公共祖先

236. 二叉树的最近公共祖先?

    private TreeNode ans = null;

    private int postOrder(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return 0;
        }

        //查看子结点的梳计个数
        int lcnt = postOrder(root.left, p, q);
        int rcnt = postOrder(root.right, p, q);
        //利用子结点返回的信息来进行处理
        //如果左边有一个，右边有一个，那么当前root就是最低公共祖先
        if (lcnt == 1 && rcnt == 1) {
            ans = root;
        } else if (lcnt == 1 || rcnt == 1) {
//               /如果左边找到一个，或者右边找到一个
//                    / 并且我等于其中某一个结点plq1
//                    /那么当前root就是最低公共祖先
            if (root == p || root == q) {
                ans = root;
            }
        }
        //返回值为以root为根的子树,统计里面的p,q结点的个数
        return lcnt + rcnt + ((root == p || root == q) ? 1 : 0);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ans = null;
        postOrder(root, p, q);
        return ans;
    }