首页 > 其他分享 >二叉树的统一迭代法

二叉树的统一迭代法

时间:2023-01-06 12:11:06浏览次数:41  
标签:node nil res len 二叉树 迭代法 stack append 统一

二叉树的统一迭代法

要想统一写法就要:将访问的节点放入栈中,把要处理的节点也放入栈中但是要做标记。

如何标记呢,就是要处理的节点放入栈之后,紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

前序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

//前序:中 左 右 因此压栈顺序为:右 左 中
func preorderTraversal(root *TreeNode) []int {
    var res []int
    var stack []*TreeNode
    if root!=nil{
        stack=append(stack,root)
    }
    
    for len(stack)>0{
        node:=stack[len(stack)-1]
        if node!=nil{
            stack=stack[:len(stack)-1]
            if node.Right!=nil{
                stack=append(stack,node.Right)//右
            }
            if node.Left!=nil{
                stack=append(stack,node.Left) //左
            }
            stack=append(stack,node)  //中
            stack=append(stack,nil)	//标记

        }else{
            stack=stack[:len(stack)-1]
            node =stack[len(stack)-1]
            stack=stack[:len(stack)-1]
            res=append(res,node.Val)
        }
    }
    return res
}


中序遍历

////中序:左 中 右 因此压栈顺序为:右 中 左
func inorderTraversal(root *TreeNode) []int {
    var res []int
    var stack []*TreeNode
    if root!=nil{
        stack=append(stack,root)
    }
    
    for len(stack)>0{
        node:=stack[len(stack)-1]
        if node!=nil{
            stack=stack[:len(stack)-1]
            if node.Right!=nil{
                stack=append(stack,node.Right)//右
            }
            stack=append(stack,node)  //中
            stack=append(stack,nil)	//标记
            if node.Left!=nil{
                stack=append(stack,node.Left) //左
            }
            

        }else{
            stack=stack[:len(stack)-1]
            node =stack[len(stack)-1]
            stack=stack[:len(stack)-1]
            res=append(res,node.Val)
        }
    }
    return res
}

后序遍历

//后边序:左 右 中 因此压栈顺序为: 中  右   左
func postorderTraversal(root *TreeNode) []int {
    var res []int
    var stack []*TreeNode
    if root!=nil{
        stack=append(stack,root)
    }
    
    for len(stack)>0{
        node:=stack[len(stack)-1]
        if node!=nil{
            stack=stack[:len(stack)-1]
            
            stack=append(stack,node)  //中
            stack=append(stack,nil)	//标记
            
            if node.Right!=nil{
                stack=append(stack,node.Right)//右
            }
            
            if node.Left!=nil{
                stack=append(stack,node.Left) //左
            }
            

        }else{
            stack=stack[:len(stack)-1]
            node =stack[len(stack)-1]
            stack=stack[:len(stack)-1]
            res=append(res,node.Val)
        }
    }
    return res
}

标签:node,nil,res,len,二叉树,迭代法,stack,append,统一
From: https://www.cnblogs.com/suehoo/p/17030071.html

相关文章

  • 144. 二叉树的前序遍历
    144.二叉树的前序遍历难度简单965收藏分享切换为英文接收动态反馈给你二叉树的根节点root,返回它节点值的前序遍历。示例1:输入:root=[1,null,2,3]输出:[1,2,3]......
  • 144. 二叉树的前序遍历
    144.二叉树的前序遍历难度简单965收藏分享切换为英文接收动态反馈给你二叉树的根节点root,返回它节点值的前序遍历。示例1:输入:root=[1,null,2,3]输出:[1,2,3]......
  • 145. 二叉树的后序遍历
    145.二叉树的后序遍历难度简单965收藏分享切换为英文接收动态反馈给你一棵二叉树的根节点root,返回其节点值的后序遍历。示例1:输入:root=[1,null,2,3]输出:[3,2......
  • 94. 二叉树的中序遍历
    94.二叉树的中序遍历难度简单1649收藏分享切换为英文接收动态反馈给定一个二叉树的根节点root,返回它的中序遍历。示例1:输入:root=[1,null,2,3]输出:[1,3,2]......
  • 每日算法之二叉树中和为某一值的路径(三)
    JZ84二叉树中和为某一值的路径(三)题目给定一个二叉树root和一个整数值sum,求该树有多少路径的的节点值之和等于sum。1.该题路径定义不需要从根节点开始,也不需要在......
  • KubeSphere 使用 OpenLDAP 进行统一认证完全指南
    作者:申红磊,青云QingCloud容器解决方案架构师,开源项目爱好者,KubeSphereMember。背景在实际使用中,会有一些用户,在不同场景中经常碰到OpenLDAP对接问题:能否对接LDAP?对接方......
  • KubeSphere 使用 OpenLDAP 进行统一认证完全指南
    作者:申红磊,青云QingCloud容器解决方案架构师,开源项目爱好者,KubeSphereMember。背景在实际使用中,会有一些用户,在不同场景中经常碰到OpenLDAP对接问题:能否对接LDA......
  • 力扣144 94 145 二叉树的前中后序遍历
    递归三要素:(1)确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数,并且还要明确每次递归的返回值是什么进而确定递归函数......
  • 二叉树遍历
    二叉树遍历递归遍历前序voidpreOrder(BTreeroot){if(root==NULL)return;visit(root);preOrder(root->left);preOrder(root->right);......
  • 4 二叉树
      满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。深度为k,有2^k-1个节点的二叉树。完全二叉树:在完全二叉树......