二叉树的各种遍历方式,包括递归和非递归的整理

1. 前、中、后三种方式的递归和非递归
2. 广度优先和层次遍历（树的深度的非递归解法）
3. 深度优先

   前序遍历

   前序遍历就是：先根节点 —> 左节点 —> 右节点

   //递归解法
   func PreOrderTraversal(root *TreeNode) []int {
   	if root == nil {
   		return nil
   	}
   	res := make([]int, 0)
   	res = append(res, root.Val)
   	if root.Left != nil {
   		res = append(res, PreOrderTraversal(root.Left)...)
   	}
   	if root.Right != nil {
   		res = append(res, PreOrderTraversal(root.Right)...)
   	}
   	return res
   }
   
   //非递归解法
   func PreOrderTraversal2(root *TreeNode) []int {
   	if root == nil {
   		return nil
   	}
   	stack := make([]*TreeNode, 0)
   	res := make([]int, 0)
   	//把根节点入栈
   	for root != nil || len(stack) > 0 {
           //不停的找做节点
   		for root != nil {
               //根节点先输出
   			res = append(res, root.Val)
   			stack = append(stack, root)
   			root = root.Left
   		}
           //出栈操作
   		root = stack[len(stack)-1]
   		stack = stack[:len(stack)-1]
           //遍历右节点
   		root = root.Right
   	}
   	return res
   }

阅读全文