【Leetcode】236. 二叉树的最近公共祖先

【Leetcode】236. 二叉树的最近公共祖先

• • 题目链接
  • 代index.php/tags-41973.html" >���

    题目链接

    【Leetcode】236. 二叉树的最近公共祖先

    （）

    代码

    /** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {    //  思路：后续遍历，如果当前跟节点包含了节点p,q，则为最近公共祖先    // 如果判断当前的包含状态呢？状态压缩    // 声明函数变量    var fun func(root *TreeNode) int    // 存放最近公共祖先    var ans *TreeNode = nil    // 后续遍历递归函数    fun = func(root *TreeNode) int{        // 如果根节点为空，则返回0，表示不包含p跟q        if root == nil {            return 0        }        // 统计当前root为根的子树中，包含p跟q的情况        state := 0        // 累加左子树的情况        state |= fun(root.Left)        // 累加右子树的情况        state |= fun(root.Right)        // 如果根节点为p，则或上1        if root == p {            state |= 1        } else if root == q {            // 如果根节点为q，则或上2            state |= 2        }        // 如果ans没有被修改过 并且 以root为根的子树包含了p跟q，则更新最近公共祖先        if ans == nil && state == 3{            ans = root        }        // 返回以root为根的子树包含p跟q的情况        return state    }    // 调用函数    fun(root)    // 返回结果    return ans}

    （）