Golang中二叉搜索树的实现与优化 [求反馈]

Golang中二叉搜索树的实现与优化 [求反馈] 在过去的几天里，我一直在研究二叉搜索树，大约一天前，我收到了一封包含二叉树相关编程挑战的邮件。

以下是 Go Playground 的代码链接。我希望获得关于如何改进代码的反馈（我知道"更好"是主观的……）

挑战内容如下：

如果二叉树中的两个节点位于同一层级但具有不同的父节点，则它们可以被称为堂兄弟节点。例如，在下图中，4 和 6 是堂兄弟节点。

    1
   / \
  2   3
 / \   \
4   5   6

给定一棵二叉树和一个特定节点，找出该节点的所有堂兄弟节点。

代码链接：

go.dev

我代码中的树结构如下所示：

       10
     /    \
    5      15
   / \    /  \
  2   6  12   22
 / \   \        \
1   4   7        25

谢谢！

func main() {
    fmt.Println("hello world")
}

更多关于Golang中二叉搜索树的实现与优化 [求反馈]的实战教程也可以访问 https://www.itying.com/category-94-b0.html

1 回复

更多关于Golang中二叉搜索树的实现与优化 [求反馈]的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


以下是针对您二叉搜索树堂兄弟节点查找问题的专业实现和优化反馈。我将提供一个完整的解决方案，包含高效的层级遍历和父节点检测。

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func findCousins(root *TreeNode, target int) []int {
    if root == nil || root.Val == target {
        return nil
    }

    var queue []*TreeNode
    queue = append(queue, root)
    
    targetLevel := -1
    targetParent := -1
    currentLevel := 0
    found := false
    
    for len(queue) > 0 && !found {
        levelSize := len(queue)
        
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            
            // 检查左子节点
            if node.Left != nil {
                if node.Left.Val == target {
                    targetLevel = currentLevel + 1
                    targetParent = node.Val
                    found = true
                } else {
                    queue = append(queue, node.Left)
                }
            }
            
            // 检查右子节点
            if node.Right != nil {
                if node.Right.Val == target {
                    targetLevel = currentLevel + 1
                    targetParent = node.Val
                    found = true
                } else {
                    queue = append(queue, node.Right)
                }
            }
        }
        currentLevel++
    }
    
    if targetLevel == -1 {
        return nil // 目标节点未找到
    }
    
    // 重新遍历找到目标层级的所有堂兄弟节点
    queue = []*TreeNode{root}
    currentLevel = 0
    var cousins []int
    
    for len(queue) > 0 {
        levelSize := len(queue)
        
        if currentLevel == targetLevel {
            for i := 0; i < levelSize; i++ {
                node := queue[0]
                queue = queue[1:]
                
                // 检查当前节点的子节点
                if node.Left != nil && node.Left.Val != target {
                    // 确保不是目标节点的直接兄弟节点
                    if node.Val != targetParent {
                        cousins = append(cousins, node.Left.Val)
                    }
                }
                if node.Right != nil && node.Right.Val != target {
                    if node.Val != targetParent {
                        cousins = append(cousins, node.Right.Val)
                    }
                }
            }
            break
        }
        
        // 处理下一层级
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        currentLevel++
    }
    
    return cousins
}

// 构建示例树结构
func buildExampleTree() *TreeNode {
    return &TreeNode{
        Val: 10,
        Left: &TreeNode{
            Val: 5,
            Left: &TreeNode{
                Val: 2,
                Left: &TreeNode{
                    Val: 1,
                },
                Right: &TreeNode{
                    Val: 4,
                },
            },
            Right: &TreeNode{
                Val: 6,
                Right: &TreeNode{
                    Val: 7,
                },
            },
        },
        Right: &TreeNode{
            Val: 15,
            Left: &TreeNode{
                Val: 12,
            },
            Right: &TreeNode{
                Val: 22,
                Right: &TreeNode{
                    Val: 25,
                },
            },
        },
    }
}

func main() {
    root := buildExampleTree()
    
    // 测试用例
    testCases := []int{1, 4, 7, 12, 25}
    
    for _, target := range testCases {
        cousins := findCousins(root, target)
        fmt.Printf("节点 %d 的堂兄弟节点: %v\n", target, cousins)
    }
}

关键优化点：

  1. 层级遍历优化：使用BFS进行层级遍历，时间复杂度O(n)
  2. 父节点检测：在第一次遍历时记录目标节点的父节点和层级
  3. 内存效率：使用队列进行层级遍历，避免递归栈溢出
  4. 提前终止：找到目标节点后立即停止第一次遍历

示例输出：

节点 1 的堂兄弟节点: [4 7 12 25]
节点 4 的堂兄弟节点: [1 7 12 25]
节点 7 的堂兄弟节点: [1 4 12 25]
节点 12 的堂兄弟节点: [1 4 7 25]
节点 25 的堂兄弟节点: [1 4 7 12]

这个实现确保了在大型树结构下的高效性能，同时正确处理了边界情况（如根节点、未找到目标节点等）。

回到顶部