image.png

    二叉树的这种题经常可以用递归的思想来解决。我不管你是怎么遍历的，我只需要明确我的递归函数的作用是什么，千万不要跳到递归函数中去用你的人脑压栈。 比如说找最近公共祖先这道题，算法的框架是这样的，我就让递归函数TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)的作用是从当前根节点向下搜索 p、q是否存在于当前节点的左右子树中，找到就返回相应的节点

    1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    2.         if (root == null || p == root || q == root) {
    3.             return root;
    4.         }
    5.         //
    6.         TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
    7.         TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
    8.         if (leftNode != null && rightNode != null) {
    9.             return root;
    10.         }
    11.         return leftNode == null ? rightNode : leftNode;
    12.     }