Traversal of binary trees

Review the previous knowledge to consolidate their 😀

The structure of the tree

structure

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right; }}Copy the code

The former sequence traversal

• recursive

  public void PreorderTraversal(TreeNode root)
  {
      if(root==null) return;
      Console.WriteLine(root.val);//<--
      PreorderTraversal(root.left);
      PreorderTraversal(root.right);
  }
  Copy the code

• The stack

  public void InorderTraversal(TreeNode root)
  {
      Stack<TreeNode> stack = new Stack<TreeNode>();
      
      while (root.Any())
      {
          TreeNode node=stack.Peek();
          if(node! =null)// the stack is pushed backwards
          {
              stack.Pop();
              if(node.right! =null) stack.Push(node.right);
              if(node.left! =null) stack.Push(node.left);
              stack.Push(node);
              stack.push(null);
          }else{
              stack.Pop();
              node=stack.Peek();
              stack.Pop();
              Console.WriteLine(node.val);//<--}}}Copy the code

In the sequence traversal

• recursive

  public void InorderTraversal(TreeNode root)
  {
      if(root==null) return;
      PreorderTraversal(root.left);
      Console.WriteLine(root.val);//<--
      PreorderTraversal(root.right);
  }
  Copy the code

• The stack

  public void InorderTraversal(TreeNode root)
  {
      Stack<TreeNode> stack = new Stack<TreeNode>();
      
      while (stack.Any())
      {
          TreeNode node=stack.Peek();
          if(node! =null)
          {
              stack.Pop();
              if(node.right! =null) stack.Push(node.right);
              stack.Push(node);
              stack.push(null);
              if(node.left! =null) stack.Push(node.left);
          }else{
              stack.Pop();
              node=stack.Peek();
              stack.Pop();
              Console.WriteLine(node.val);//<--}}}Copy the code

After the sequence traversal

• recursive

  public void PostorderTraversal(TreeNode root)
  {
      if(root==null) return;
      PreorderTraversal(root.left);
      PreorderTraversal(root.right);
      Console.WriteLine(root.val);//<--
  }
  Copy the code

• The stack

  public void InorderTraversal(TreeNode root)
  {
      Stack<TreeNode> stack = new Stack<TreeNode>();
      
      while (stack.Any())
      {
          TreeNode node=stack.Peek();
          if(node! =null)// the stack is pushed backwards
          {
              stack.Pop();
              stack.Push(node);
              stack.push(null);
              
              if(node.right! =null) stack.Push(node.right);
              if(node.left! =null) stack.Push(node.left);
          }else{ stack.Pop(); node=stack.Peek(); stack.Pop(); Console.WriteLine(node.val); }}}Copy the code

conclusion

Before always used recursion, stack method forget 😀, so the stack method is also need to sum up, simply sum up together.

Urge oneself to do this summary, let oneself be familiar with, do not forget again, end scatter flower 🎉🎉🎉