leetcode 树 相关

二叉树的前序遍历

1、递归方式

func preorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    preorder(root, &result)
    return result
}
func preorder(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }

    *result = append(*result, root.Val)
    preorder(root.Left, result)
    preorder(root.Right, result)
}

二叉树的中序遍历

1、递归方式

func inorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    inorder(root, &result)
    return result
}
func inorder(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }
    inorder(root.Left, result)
    *result = append(*result, root.Val)
    inorder(root.Right, result)
}

二叉树的后序遍历

1、递归方式

func postorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    postorder(root, &result)
    return result
}
func postorder(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }

    postorder(root.Left, result)
    postorder(root.Right, result)
    *result = append(*result, root.Val)
}

二叉树的层次遍历

1、使用队列，BFS

func levelOrder(root *TreeNode) [][]int {
    result := make([][]int, 0)
    if root == nil {
        return result
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    for len(queue) > 0 {
        level := make([]int, 0)
        queueSize := len(queue)
        for i := 0; i < queueSize; i++ {
            root := queue[0]
            queue = queue[1:]
            val := root.Val
            level = append(level, val)
            if root.Left != nil {
                queue = append(queue, root.Left)
            }
            if root.Right != nil {
                queue = append(queue, root.Right)
            }
        }
        result = append(result, level)
    }
    return result
}

相同的树

正常递归判断就行

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    return sameTree(p, q)
}
func sameTree(p *TreeNode, q *TreeNode) bool {
    if p != nil && q != nil && p.Val != q.Val {
        return false
    }
    if p== nil && q==nil {
        return true
    }
    if p==nil && q!=nil || p!=nil&&q==nil {
        return false
    }
    left := sameTree(p.Left, q.Left)
    right := sameTree(p.Right, q.Right)
    return left && right
}

对称二叉树

一种是递归方式

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return symmetric(root.Left, root.Right)
}
func symmetric(p *TreeNode, q *TreeNode) bool {
    if p != nil && q != nil && p.Val != q.Val {
        return false
    }
    if p == nil && q == nil {
        return true
    }
    if p == nil && q != nil || p != nil && q == nil {
        return false
    }
    left := symmetric(p.Left, q.Right)
    right := symmetric(p.Right, q.Left)
    return left && right
}

一种是利用层次遍历，层次遍历是先加左子树再加右子树到队列。这里可以先加左子树的左子树 再加右子树的右子树

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    queue = append(queue, root)
    for len(queue) > 0 {
        left := queue[0]
        right := queue[1]
        queue = queue[2:]
        if left == nil && right == nil {
            continue
        }
        if left != nil && right == nil || left == nil && right != nil {
            return false
        }
        if left.Val == right.Val {
            queue = append(queue, left.Left)
            queue = append(queue, right.Right)
            queue = append(queue, left.Right)
            queue = append(queue, right.Left)
        } else {
            return false
        }
    }

    return true
}

文章永久链接：https://tech.souyunku.com/45192