236
这道题的思路是对于任意的一个祖先,一定是一棵树,至少存在一个子树,所以遍历子树,如果子树是p、q那么就返回标记true,如果两个子树都返回true,那么该节点就一定是祖先。此外,当某个祖先自己也是p(q)的一员,那么只要其中一棵子树满足要求,那么这个节点也可以返回。
这里记录一下对于后序遍历中节点的理解,每次理解中节点的动作都有点转不过弯。理解中节点可以把树的每一个叶子节点当作一个完整的二叉树,只不过这个二叉树的左右子树都是NULL,所以在写单层递逻辑的时候,就可以围绕这个中间节点直接写,想想如何实现就行。
124
这道题的思路是后序递归每一个子树,然后记录每一个子树能得到的最大值,递归完之后就回溯到上一个节点,因为节点不能重复,所以返回值是这个子树的根节点和其左右子树中的最大值。此外,如果某个节点的左右子树是负数,那么这个子树就不参与,在代码上就是让这个子树的返回值和0作比较取最大值。
46
这道题属于回溯问题,思路上比较简单就是按照顺序分别遍历数组,有点暴力解法的意思,只不过这里需要记录已经遍历过的节点,这样在递归的时候就能不会再遍历重复,我采用的是used数组,每次当元素遍历过了就将对应位置改为true,下一次递归碰到true就跳过,否则就继续。