二叉树

二叉树遍历

1.以根访问顺序决定是什么“序”遍历（仅适用于前序，中序，后序）
2.左子树优先于右子树（一般遍历均满足此条件）

DFS深度优先搜索

Depth-First-Search。
一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。
一般步骤(非递归方法会用到栈)为

首先将根节点放入stack中。
从stack中取出第一个节点，并检验它是否为目标。
- 如果找到目标，则结束搜寻并回传结果。
- 否则将它某一个尚未检验过的直接子节点加入stack中。
重复步骤2。
如果不存在未检测过的直接子节点。
- 将上一级节点加入stack中。
- 重复步骤2。
重复步骤4。
若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

1.前序遍历

符合DFS深度优先搜索的一种二叉树遍历算法。
先访问根节点，再前序遍历左节点，再前序遍历右节点。

递归实现

public class BinaryTreeNode {
  public int val;
  public BinaryTreeNode left;
  public BinaryTreeNode right;

  public BinaryTreeNode(int val){
      this.val = val;
      left = null;
      right = null;
  }

  public static void preorderTraversal(BinaryTreeNode root){
      if(root == null){
          return;
      }
      System.out.println(root.val);
      preorderTraversal(root.left);
      preorderTraversal(root.right);
  }
}

非递归实现

  public static void preorderTraversal(BinaryTreeNode root){
      if(root == null){
          return;
      }
      // 
      Stack<BinaryTreeNode> stack = new Stack<>();
      stack.push(root);

      while (!stack.isEmpty()){
          BinaryTreeNode node = stack.pop();
          System.out.println(node.val);

          if(node.right != null){
              stack.push(node.right);
          }

          if(node.left != null){
              stack.push(node.left);
          }
      }
  }

实测

      /******
          3
         / \
       1    4
      / \  / \
     -1 2
       ******/
  //打印的结果为：3 1 -1 2 4
  BinaryTreeNode.preorderTraversal(root);

2.中序遍历

符合DFS深度优先搜索的一种二叉树遍历算法。
先中序遍历左子树，再访问根节点，再中序遍历右节点。

递归实现

  public static void inorderTraversal(BinaryTreeNode root){
      if(root == null){
          return;
      }
      inorderTraversal(root.left);
      System.out.println(root.val);
      inorderTraversal(root.right);
  }

实测

      /***************************
          3
         / \
       1    4
      / \  / \
     -1 2
       *************************/
      //打印的结果为：-1 1 2 3 4
      //可以看出中序遍历能将二叉搜索树按大小顺序遍历
      BinaryTreeNode.inorderTraversal(root);

3.后序遍历

符合DFS深度优先搜索的一种二叉树遍历算法。
先后序遍历左子树，再后序遍历右子树，再访问根节点。

递归实现

  public static void postorderTraversal(BinaryTreeNode root){
      if(root == null){
          return;
      }
      postorderTraversal(root.left);
      postorderTraversal(root.right);
      System.out.println(root.val);
  }

实测

      /***************************
          3
         / \
       1    4
      / \  / \
     -1 2
       *************************/
      //打印的结果为：-1 2 1 4 3
      BinaryTreeNode.postorderTraversal(root);

BFS广度优先搜索

Breadth-First Search。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
一般步骤为

首先将根节点放入队列中。
从队列中取出第一个节点，并检验它是否为目标。
- 如果找到目标，则结束搜索并回传结果。
- 否则将它所有尚未检验过的直接子节点加入队列中。
若队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
重复步骤2。

1.层次遍历

符合广度优先搜索的一种二叉树遍历算法。

    public static void levelOrderTraversal(BinaryTreeNode root){
        if(root == null){
            return;
        }
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            System.out.println(queue.peek().val);

            BinaryTreeNode node = queue.peek();

            if(node.left != null){
                queue.offer(node.left);
            }

            if(node.right != null){
                queue.offer(node.right);
            }
            queue.poll();
        }
    }

实测

      /***************************
          3
         / \
       1    4
      / \  / \
     -1 2
       *************************/
      //打印结果为：3 1 4 -1 2
      BinaryTreeNode.levelOrderTraversal(root);

二叉树