二叉树

三种常用遍历方式(前序，中序，后序)

前序遍历（伪代码）

根->左->右

递归

  1. void pre_order(Node root) {
  2.     // 处理根节点
  3.     process(root);
  4.     // 遍历左子树
  5.     pre_order(root.left);
  6.     // 遍历右子树
  7.     pre_order(root.right);
  8. }

非递归

  1. void pre_order_iter(Node root) {
  2.     // 根节点入栈
  3.     stack.push(root);
  4.     while !stack.is_empty() {
  5.         // 弹出栈顶节点
  6.         let node = stack.pop();
  7.         // 处理节点 process(node);
  8.         if node.right != null {
  9.             // 将右孩子入栈
  10.              stack.push(node.right);   
  11.         }
  13.         if node.left != null {
  14.             // 左孩子入栈
  15.              stack.push(node.left);   
  16.         }
  17.     }
  18. }

中序遍历（伪代码）

左->根->右

递归

  1. void in_order(Node root) {
  2.     // 遍历左子树
  3.     in_order(root.left);
  4.     // 处理根节点
  5.     process(root);
  6.     // 遍历右子树
  7.     in_order(root.right);
  8. }

非递归

  1. void push_left_childs(Stack stack, Node root) {
  2.     while root != NULL {
  3.          stack.push(root);
  4.         root = root.left;
  5.     }
  6. }
  8. void in_order_iter(Node root) {
  9.     Stack stack;
  10.     push_left_childs(stack, root);
  11.     while !stack.is_empty() {
  12.         // 弹出栈顶节点
  13.         let node = stack.pop();
  14.         // 处理节点 
  15.         process(node); 
  17.         // 处理右子树
  18.         if node.right != NULL{
  19.                push_left_childs(stack, node.right);
  20.         }
  21.     }
  22. }

后序遍历（伪代码）

左->右->根

递归

  1. void post_order(Node root) {
  2.     // 遍历左子树
  3.     post_order(root.left);
  4.     // 遍历右子树
  5.     post_order(root.right);
  6.     // 处理根节点
  7.     process(root);
  8. }

非递归

  1. void post_order_iter(Node root) {
  2.     Stack stack;
  3.     stack.push(root);
  4.     // 记录上一个处理节点，来判断节点的子节点是否已处理
  5.     Node pre = NULL;
  6.     while !stack.is_empty() {
  7.         // 获取栈顶节点
  8.         let node = stack.top(); 
  9.         if node.left == NULL && node.right == NULL || node.left == pre || node .right == pre {
  10.              // 处理节点
  11.             process(node);
  12.             stack.pop();
  13.             pre = node;
  14.         } else {
  15.             if node.right != NULL {
  16.                 stack.push(node.right);
  17.             } 
  18.             if node.left != NULL {
  19.                 stack.push(node.left);
  20.             }
  21.         }
  22.     }
  23. }

层次遍历(BFS)

  1. void level_order_v1(Node root) {
  2.      Queue queue;
  3.     queue.push_back(root);
  4.     while !queue.is_empty() {
  5.         let node = queue.pop_front();
  6.         // 处理节点
  7.         process(node);
  9.         if node.left != NULL {
  10.             queue.push_back(node.left);
  11.         }
  13.         if node.right != NULL {
  14.             queue.push_back(node.right);
  15.         }
  16.     }
  17. }
  19. void level_order_v2(Node root) {
  20.      Queue queue;
  21.     queue.push_back(root);
  22.     while !queue.is_empty() {
  23.         let n = queue.len();
  24.         // 可以统计每层数据
  25.         for i = 0; i < n; i++ {
  26.             let node = queue.pop_front();
  27.             // 处理节点
  28.             process(node);
  30.             if node.left != NULL {
  31.                 queue.push_back(node.left);
  32.             }
  34.             if node.right != NULL {
  35.                 queue.push_back(node.right);
  36.             }
  37.         }
  38.     }
  39. }

技巧

例题

二叉树的最近公共祖先