最近公共节点

题目2：二叉树的最近公共祖先
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。

例如，给定如下二叉树:

  3
 / \
5   1

/ \ /
6 2 0 8
/
7 4
示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。
因为根据定义最近公共祖先节点可以为节点本身。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 如果根节点为空或者根节点就是p或q，直接返回根节点
    if (root == null || root == p || root == q) return root;

    // 在左子树中查找p和q
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    // 在右子树中查找p和q
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    // 如果左子树和右子树都找到了p和q，那么最近公共祖先就是该节点
    if (left != null && right != null) return root;

    // 如果只在左子树中找到了p和q，那么最近公共祖先在左子树中
    if (left != null) return left;

    // 如果只在右子树中找到了p和q，那么最近公共祖先在右子树中
    return right;
}

#中序遍历

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>(); // 存储结果的列表
if (root == null) {
return result; // 如果根节点为空，直接返回结果列表
}
result.addAll(inorderTraversal(root.left)); // 递归遍历左子树，并将结果加入结果列表
result.add(root.val); // 将当前节点的值加入结果列表
result.addAll(inorderTraversal(root.right)); // 递归遍历右子树，并将结果加入结果列表
return result; // 返回结果列表
}
}

#二叉树对称

class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetricHelper(root.left, root.right);
}

private boolean isSymmetricHelper(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null || left.val != right.val) {
        return false;
    }
    return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
}

}