【TODO】【简单】94. 二叉树的中序遍历

2023-12-21 21:40:26

题目

94. 二叉树的中序遍历
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:
输入:root = []
输出:[]

示例 3:
输入:root = [1]
输出:[1]

提示:
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

解题

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    if root==nil{
        return []int{}
    }

    re := []int{}

    if root.Left != nil{
        re = append(re, inorderTraversal(root.Left)...) 
        
    }
    re = append(re, root.Val)
    if root.Right != nil{
        re = append(re, inorderTraversal(root.Right)...)
    }
    
    return re      
}

题解

方法一:递归

真简洁

func inorderTraversal(root *TreeNode) (res []int) {
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)
		res = append(res, node.Val)
		inorder(node.Right)
	}
	inorder(root)
	return
}

作者:力扣官方题解
链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/412886/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

n:节点个数
时间:O(n)
空间:O(n)

方法二:迭代

2

func inorderTraversal(root *TreeNode) (res []int) {
	stack := []*TreeNode{}
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, root.Val)
		root = root.Right
	}
	return
}

作者:力扣官方题解
链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/412886/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

时间:O(n)
空间:O(n)

方法三:Morris 中序遍历

func inorderTraversal(root *TreeNode) (res []int) {
	for root != nil {
		if root.Left != nil {
			// predecessor 节点表示当前 root 节点向左走一步,然后一直向右走至无法走为止的节点
			predecessor := root.Left
			for predecessor.Right != nil && predecessor.Right != root {
				// 有右子树且没有设置过指向 root,则继续向右走
				predecessor = predecessor.Right
			}
			if predecessor.Right == nil {
				// 将 predecessor 的右指针指向 root,这样后面遍历完左子树 root.Left 后,就能通过这个指向回到 root
				predecessor.Right = root
				// 遍历左子树
				root = root.Left
			} else { // predecessor 的右指针已经指向了 root,则表示左子树 root.Left 已经访问完了
				res = append(res, root.Val)
				// 恢复原样
				predecessor.Right = nil
				// 遍历右子树
				root = root.Right
			}
		} else { // 没有左子树
			res = append(res, root.Val)
			// 若有右子树,则遍历右子树
			// 若没有右子树,则整颗左子树已遍历完,root 会通过之前设置的指向回到这颗子树的父节点
			root = root.Right
		}
	}
	return
}

作者:力扣官方题解
链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

时间:O(n)
空间:O(1)

长进

  1. 树的方法还差着呢,尤其迭代法和Morris中序遍历方法。还需要加以练习。

文章来源:https://blog.csdn.net/Miller_6/article/details/135097482
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。