一：二叉树的右视图

image-20251008174255364

1. 深度优先搜索

通过另一个深度栈来维护每一层唯一的可见值，这个值为后添加的右节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        unordered_map<int, int> hashMap;
        stack<TreeNode*> stk;
        stack<int> stkDepth;
        int maxDepth = 0;
        stk.push(root);
        stkDepth.push(1);
        while (stk.empty() == false)
        {
            TreeNode* node = stk.top();
            stk.pop();
            int depth = stkDepth.top(); stkDepth.pop();
            if (node != nullptr)
            {
                maxDepth = max(maxDepth, depth);
                if (hashMap.count(depth) == false) hashMap[depth] = node->val;
                stk.push(node->left);
                stk.push(node->right);      // 优先弹出右节点
                stkDepth.push(depth + 1);
                stkDepth.push(depth + 1);
            }
        }
        vector<int> result;
        for (int i = 1; i <= maxDepth; ++i) result.emplace_back(hashMap[i]);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> hashMap = new HashMap<>();
        Deque<TreeNode> stk = new LinkedList<>();
        Deque<Integer> stkDepth = new LinkedList<>();
        int maxDepth = 0;
        stk.push(root);
        stkDepth.push(1);
        while (stk.isEmpty() == false)
        {
            TreeNode node = stk.pop();
            int depth = stkDepth.pop();
            if (node != null)
            {
                maxDepth = Math.max(maxDepth, depth);
                if (hashMap.containsKey(depth) == false) hashMap.put(depth, node.val);
                stk.push(node.left);
                stk.push(node.right);      // 优先弹出右节点
                stkDepth.push(depth + 1);
                stkDepth.push(depth + 1);
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= maxDepth; ++i) result.add(hashMap.get(i));
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        hashMap = dict()
        maxDepth = 0
        stack = [(root, 1)]
        while stack:
            node, depth = stack.pop()
            if (node != None):
                maxDepth = max(maxDepth, depth)
                if (depth not in hashMap): hashMap[depth] = node.val    
                stack.append((node.left, depth + 1))
                stack.append((node.right, depth + 1))
        result = []
        for i in range(1, maxDepth + 1): result.append(hashMap[i])
        return result

image-20251008174936698

2. 广度优先搜索

类似于深度，这里使用队列执行先进先出，因此从左节点开始向右遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        unordered_map<int, int> hashMap;
        queue<TreeNode*> stk;
        queue<int> stkDepth;
        int maxDepth = 0;
        stk.push(root);
        stkDepth.push(1);
        while (stk.empty() == false)
        {
            TreeNode* node = stk.front();
            stk.pop();
            int depth = stkDepth.front(); stkDepth.pop();
            if (node != nullptr)
            {
                maxDepth = max(maxDepth, depth);
                hashMap[depth] = node->val;			// 最后一个节点为可见节点
                stk.push(node->left);
                stk.push(node->right);      		// 先弹出左节点
                stkDepth.push(depth + 1);
                stkDepth.push(depth + 1);
            }
        }
        vector<int> result;
        for (int i = 1; i <= maxDepth; ++i) result.emplace_back(hashMap[i]);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> hashMap = new HashMap<>();
        Queue<TreeNode> stk = new LinkedList<>();
        Queue<Integer> stkDepth = new LinkedList<>();
        int maxDepth = 0;
        stk.add(root);
        stkDepth.add(1);
        while (stk.isEmpty() == false)
        {
            TreeNode node = stk.remove();
            int depth = stkDepth.remove();
            if (node != null)
            {
                maxDepth = Math.max(maxDepth, depth);
                hashMap.put(depth, node.val);
                stk.add(node.left);
                stk.add(node.right);      // 优先弹出右节点
                stkDepth.add(depth + 1);
                stkDepth.add(depth + 1);
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= maxDepth; ++i) result.add(hashMap.get(i));
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        hashMap = dict()
        maxDepth = 0
        queue = deque([(root, 1)])
        while queue:
            node, depth = queue.popleft()
            if (node != None):
                maxDepth = max(maxDepth, depth)
                hashMap[depth] = node.val    
                queue.append((node.left, depth + 1))
                queue.append((node.right, depth + 1))
        result = []
        for i in range(1, maxDepth + 1): result.append(hashMap[i])
        return result

image-20251008174928117

二：二叉树展开为链表

image-20251008174308698

1. 前序遍历

前序遍历得到所有节点的数组，然后逐一构建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> listTree;
        PreOrder(root, listTree);
        for (int i = 1; i < listTree.size(); ++i)
        {
            TreeNode* pre = listTree[i - 1];
            TreeNode* cur = listTree[i];
            pre->right = cur;
            pre->left = nullptr;
        }
    }
    void PreOrder(TreeNode* node, vector<TreeNode*>& listTree)
    {
        if (node != nullptr) 
        {
            listTree.emplace_back(node);
            PreOrder(node->left, listTree);
            PreOrder(node->right, listTree);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> listTree = new ArrayList<>();
        PreOrder(root, listTree);
        for (int i = 1; i < listTree.size(); ++i)
        {
            TreeNode pre = listTree.get(i - 1);
            TreeNode cur = listTree.get(i);
            pre.right = cur;
            pre.left = null;
        }
    }
    public void PreOrder(TreeNode node, List<TreeNode> listTree)
    {
        if (node != null) 
        {
            listTree.add(node);
            PreOrder(node.left, listTree);
            PreOrder(node.right, listTree);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        listTree = list()
        self.PreOrder(root, listTree)
        for i in range(1, len(listTree)):
            pre = listTree[i - 1]
            cur = listTree[i]
            pre.right = cur
            pre.left = None
    def PreOrder(self, node, listTree):
        if (node != None):
            listTree.append(node)
            self.PreOrder(node.left, listTree)
            self.PreOrder(node.right, listTree)

image-20251008174827827

2. 前序遍历和展开同步进行

不使用额外数组，使用栈来使遍历和创建新链表同时进行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;
        stack<TreeNode*> stk;
        stk.push(root);
        TreeNode* pre = nullptr;
        while (stk.empty() == false)
        {
            TreeNode* cur = stk.top();
            stk.pop();
            if (pre != nullptr)
            {
                pre->left = nullptr;
                pre->right = cur;
            }
            if (cur->right != nullptr) stk.push(cur->right);     // 先进右节点出栈可以先处理左节点
            if (cur->left != nullptr) stk.push(cur->left);
            pre = cur;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Deque<TreeNode> stk = new LinkedList<>();
        stk.push(root);
        TreeNode pre = null;
        while (stk.isEmpty() == false)
        {
            TreeNode cur = stk.pop();
            if (pre != null)
            {
                pre.left = null;
                pre.right = cur;
            }
            if (cur.right != null) stk.push(cur.right);     // 先进右节点出栈可以先处理左节点
            if (cur.left != null) stk.push(cur.left);
            pre = cur;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if (root == None): return
        stk = [root]
        pre = None
        while (stk):
            cur = stk.pop()
            if (pre != None):
                pre.left = None
                pre.right = cur
            if (cur.right != None): stk.append(cur.right)     
            if (cur.left != None): stk.append(cur.left)
            pre = cur

image-20251008174807890

3. 寻找前驱节点

这个方法有点类似于二叉树的中序遍历中的Morris方法，通过将左子树最后的右节点指向当前节点的右节点，从而建立连接关系，相当于更改了当前链表的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;
        auto cur = root;
        while (cur != nullptr)
        {
            if (cur->left != nullptr)
            {
                auto node = cur->left;
                auto next = node;
                while (node->right != nullptr) node = node->right;      // 一直右移找到当前节点的前继结点
                node->right = cur->right;
                cur->left = nullptr;
                cur->right = next;
            }
            cur = cur->right;
        }
    }
};	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        TreeNode cur = root;
        while (cur != null)
        {
            if (cur.left != null)
            {
                TreeNode node = cur.left;
                TreeNode next = node;
                while (node.right != null) node = node.right;      // 一直右移找到当前节点的前继结点
                node.right = cur.right;
                cur.left = null;
                cur.right = next;
            }
            cur = cur.right;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if (root == None): return
        cur = root
        while (cur != None):
            if (cur.left != None):
                node = cur.left
                next = node
                while (node.right != None): node = node.right     
                node.right = cur.right
                cur.left = None
                cur.right = next
            cur = cur.right

image-20251008174815971

三：从前序与中序遍历序列构造二叉树

image-20251008174319412

1. 递归

通过前序遍历找到中序遍历的根节点，然后左右划分依次递归，需要先处理左边，因为先序遍历根节点之后是左子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
private:
    unordered_map<int, int> index;

public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        int preorder_root = preorder_left;
        int inorder_root = index[preorder[preorder_root]];
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        int size_left_subtree = inorder_root - inorder_left;
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    private Map<Integer, Integer> indexMap;
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }
        int preorder_root = preorder_left;
        int inorder_root = indexMap.get(preorder[preorder_root]);
        TreeNode root = new TreeNode(preorder[preorder_root]);
        int size_left_subtree = inorder_root - inorder_left;
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
            if preorder_left > preorder_right:
                return None
            preorder_root = preorder_left
            inorder_root = index[preorder[preorder_root]]
            root = TreeNode(preorder[preorder_root])
            size_left_subtree = inorder_root - inorder_left
            root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
            root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
            return root
        n = len(preorder)
        index = {element: i for i, element in enumerate(inorder)}
        return myBuildTree(0, n - 1, 0, n - 1)

image-20251008174646786

2. 迭代

这个解法巧妙的利用了先序和中序的特点，先序从根节点先到达最后一个左节点，中序则从最后一个左节点开始，当先序的某个节点和中序的第一个相等意味着当前节点的左子树结束，此时用栈来维护没有处理右子树的节点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (!preorder.size()) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[0]);
        stack<TreeNode*> stk;
        stk.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.size(); ++i) {
            int preorderVal = preorder[i];
            TreeNode* node = stk.top();
            if (node->val != inorder[inorderIndex]) {
                node->left = new TreeNode(preorderVal);
                stk.push(node->left);
            }
            else {
                while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {
                    node = stk.top();
                    stk.pop();
                    ++inorderIndex;
                }
                node->right = new TreeNode(preorderVal);
                stk.push(node->right);
            }
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        stack = [root]
        inorderIndex = 0
        for i in range(1, len(preorder)):
            preorderVal = preorder[i]
            node = stack[-1]
            if node.val != inorder[inorderIndex]:
                node.left = TreeNode(preorderVal)
                stack.append(node.left)
            else:
                while stack and stack[-1].val == inorder[inorderIndex]:
                    node = stack.pop()
                    inorderIndex += 1
                node.right = TreeNode(preorderVal)
                stack.append(node.right)
        return root

image-20251008174657198

四：路径总和 III

image-20251008174332337

1. 深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int rootSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }

        int ret = 0;
        if (root->val == targetSum) {
            ret++;
        } 

        ret += rootSum(root->left, targetSum - root->val);
        ret += rootSum(root->right, targetSum - root->val);
        return ret;
    }
    int pathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }
        
        int ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int pathSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = rootSum(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public int rootSum(TreeNode root, long targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        } 

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        def rootSum(root, targetSum):
            if root is None:
                return 0

            ret = 0
            if root.val == targetSum:
                ret += 1

            ret += rootSum(root.left, targetSum - root.val)
            ret += rootSum(root.right, targetSum - root.val)
            return ret
        
        if root is None:
            return 0
            
        ret = rootSum(root, targetSum)
        ret += self.pathSum(root.left, targetSum)
        ret += self.pathSum(root.right, targetSum)
        return ret

image-20251008174546646

2. 前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    unordered_map<long long, int> prefix;
    int dfs(TreeNode *root, long long curr, int targetSum) {
        if (!root) {
            return 0;
        }
        int ret = 0;
        curr += root->val;
        if (prefix.count(curr - targetSum)) {
            ret = prefix[curr - targetSum];
        }
        prefix[curr]++;
        ret += dfs(root->left, curr, targetSum);
        ret += dfs(root->right, curr, targetSum);
        prefix[curr]--;
        return ret;
    }
    int pathSum(TreeNode* root, int targetSum) {
        prefix[0] = 1;
        return dfs(root, 0, targetSum);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }
        int ret = 0;
        curr += root.val;
        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        prefix = collections.defaultdict(int)
        prefix[0] = 1
        def dfs(root, curr):
            if not root:
                return 0
            ret = 0
            curr += root.val
            ret += prefix[curr - targetSum]
            prefix[curr] += 1
            ret += dfs(root.left, curr)
            ret += dfs(root.right, curr)
            prefix[curr] -= 1
            return ret
        return dfs(root, 0)

image-20251008174605351

五：二叉树的最近公共祖先

image-20251008174346146

1. 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private TreeNode ans;
    public Solution() {
        this.ans = null;
    }
    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root.val == p.val || root.val == q.val);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def __init__(self):
        self.ans = None
    def dfs(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> bool:
        if not root:
            return False
        lson = self.dfs(root.left, p, q)
        rson = self.dfs(root.right, p, q)
        if (lson and rson) or ((root.val == p.val or root.val == q.val) and (lson or rson)):
            self.ans = root
        return lson or rson or (root.val == p.val or root.val == q.val)
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.dfs(root, p, q)
        return self.ans

image-20251008174439272

2. 存储父节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    unordered_map<int, TreeNode*> fa;
    unordered_map<int, bool> vis;
    void dfs(TreeNode* root){
        if (root->left != nullptr) {
            fa[root->left->val] = root;
            dfs(root->left);
        }
        if (root->right != nullptr) {
            fa[root->right->val] = root;
            dfs(root->right);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fa[root->val] = nullptr;
        dfs(root);
        while (p != nullptr) {
            vis[p->val] = true;
            p = fa[p->val];
        }
        while (q != nullptr) {
            if (vis[q->val]) return q;
            q = fa[q->val];
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();
    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def __init__(self):
        self.fa = {}
        self.visited = set()
    def dfs(self, root: 'TreeNode'):
        if root.left:
            self.fa[root.left.val] = root
            self.dfs(root.left)
        if root.right:
            self.fa[root.right.val] = root
            self.dfs(root.right)
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.fa[root.val] = None  # 根节点没有父节点
        self.dfs(root)
        while p:
            self.visited.add(p.val)
            p = self.fa.get(p.val) # 使用.get()避免键不存在时出错
        while q:
            if q.val in self.visited:
                return q
            q = self.fa.get(q.val)
        return None

image-20251008174428002