【golang必备算法】二叉树遍历(迭代)
二叉树遍历(迭代)
func preorderTraversal(root *TreeNode) []int { res := []int{ } if root == nil{ return res } strack := []*TreeNode{ } strack = append(strack,root) for len(strack)>0{ temp := strack[len(strack)-1] res = append(res,temp.Val) strack = strack[:len(strack)-1] //因为是栈,先放右节点 if temp.Right != nil{ strack = append(strack,temp.Right) } if temp.Left != nil{ strack = append(strack,temp.Left) } } return res }
func inorderTraversal(root *TreeNode) []int { strack := []*TreeNode{ } cur := root res := []int{ } for cur!=nil || len(strack)>0{ if cur != nil{ strack = append(strack,cur) cur = cur.Left }else{ temp := strack[len(strack)-1] strack = strack[:len(strack)-1] res = append(res,temp.Val) cur = temp.Right } } return res }
后序遍历是 左右中 ,而前序遍历是 中左右 ,所以把前序遍历顺序改一下再反转就是后序遍历
func postorderTraversal(root *TreeNode) []int { res := []int{ } if root == nil{ return res } strack := []*TreeNode{ } strack = append(strack,root) for len(strack)>0{ temp := strack[len(strack)-1] res = append(res,temp.Val) strack = strack[:len(strack)-1] //这里先放左节点,再放右节点,得到的就是 中右左,再反转就是后序遍历 if temp.Left != nil{ strack = append(strack,temp.Left) } if temp.Right != nil{ strack = append(strack,temp.Right) } } return fanzhuan(res) } func fanzhuan(res []int)[]int{ for i:=0;i<len(res)/2;i++{ res[i],res[len(res)-1-i] = res[len(res)-1-i],res[i] } return res }