题目

前序遍历

中序遍历

后序遍历

1.二叉树种类

  • 满二叉树
    如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。
  • 完全二叉树
    完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^h -1 个节点。
  • 二叉搜索树
    二叉搜索树是一个有数值的树,是一个有序树。
  • 平衡二叉搜索树
    平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两棵子树都是一棵平衡二叉树。

2.遍历方式

  • 深度优先

Go版(递归)

2.1前序遍历

// preorderTraversal 前序遍历
func preorderTraversal(root *TreeNode) (res []int) {
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode) {
        if node == nil {
            return
        }
        res = append(res, node.Val)
        traversal(node.Left)
        traversal(node.Right)
    }
    traversal(root)
    return res
}

2.2中序遍历

// inorderTraversal 中序遍历
func inorderTraversal(root *TreeNode) (res []int) {
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode) {
        if node == nil {
            return
        }
        traversal(node.Left)
        res = append(res, node.Val)
        traversal(node.Right)
    }
    traversal(root)
    return res
}

2.3后序遍历

// postorderTraversal 后序遍历
func postorderTraversal(root *TreeNode) (res []int) {
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode) {
        if node == nil {
            return
        }
        traversal(node.Left)
        traversal(node.Right)
        res = append(res, node.Val)
    }
    traversal(root)
    return res
}

Go版——迭代(非递归)

1.前序遍历

// 前序遍历

// preorderTraversal 非递归遍历,迭代遍历
// 前序遍历
func preorderTraversal2(root *TreeNode) (res []int) {
    if root == nil {
        return res
    }
    stack := list.New()
    stack.PushBack(root)
    for stack.Len() > 0 {
        // stack.Back()返回最后一个元素,而且这里必须做类型断言
        node := stack.Remove(stack.Back()).(*TreeNode)
        //fmt.Printf("%T:", node)
        res = append(res, node.Val)
        if node.Right != nil {
            stack.PushBack(node.Right)
        }
        if node.Left != nil {
            stack.PushBack(node.Left)
        }
    }
    return res
}

2.后序遍历

// 后序遍历
func postorderTraversal2(root *TreeNode) (res []int) {
    stack := list.New()
    if root == nil {
        return res
    }
    stack.PushBack(root)
    for stack.Len() > 0 {
        node := stack.Remove(stack.Back()).(*TreeNode)
        res = append(res, node.Val)
        if node.Left != nil {
            stack.PushBack(node.Left)
        }
        if node.Right != nil {
            stack.PushBack(node.Right)
        }
    }
    reverse(res)
    return res
}
func reverse(res []int) {
    left, right := 0, len(res)-1
    for right > left {
        res[left], res[right] = res[right], res[left]
        left++
        right--
    }
}

3.中序遍历

// 中序遍历:左中右
func inorderTraversal2(root *TreeNode) (res []int) {
    if root == nil {
        return res
    }
    cur := root
    stack := list.New()
    // 使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素
    for cur != nil || stack.Len() > 0 {
        if cur != nil {
            // 只要当前cur不为空,就把当前节点添加进栈,
            stack.PushBack(cur)
            // 然后一直遍历
            cur = cur.Left
        } else {
            // 如果当前节点为空,那么就从栈弹出元素
            cur = stack.Remove(stack.Back()).(*TreeNode)
            // 然后节点添加进返回的数组
            res = append(res, cur.Val)
            //然后再继续遍历
            cur = cur.Right
        }
    }
    return res
}

python版

2.4前序遍历

class Solution:
    def preordertraversal(self, root:TreeNode)->List[int]:
        res = []

        def traversal(root:TreeNode):
            if root==None:
                return
            res.append(root.val)
            traversal(root.left)
            traversal(root.right)

        traversal(root)
        return res

2.5中序遍历

class Solution:
    def inordertraversal(self, root:TreeNode)->List[int]:
        res = []

        def traversal(root:TreeNode):
            if root==None:
                return
            traversal(root.left)
            res.append(root.val)
            traversal(root.right)

        traversal(root)
        return res

2.6后序遍历

class Solution:

    def postordertraversal(self, root:TreeNode):
        res = []

        def traversal(root:TreeNode):
            if root==None:
                return
            traversal(root.left)
            traversal(root.right)
            res.append(root.val)
        traversal(root)
        return res
  • 广度优先
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

ICP备案号: 辽ICP备20003309号