二叉树理论基础

1. 种类

   1. 满二叉树，数上只有度为0或2的节点
   2. 完全二叉树，(h - 1)层都满了，h层都集中在左侧若干位置

2. 存储方式

   1. 链式存储，指针
   2. 顺序存储，数组

3. 遍历方式

   1. 深度优先
      1. 前序遍历(递归，迭代)
      2. 中序遍历(递归，迭代)
      3. 后序遍历(递归，迭代)
      4. 前中后其实表示的是 中间节点的位置
   2. 广度优先
      1. 层次遍历

4. 二叉树的定义

   public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
   }
   

二叉树的递归遍历

参考144. 二叉树的前序遍历 - 力扣（LeetCode）

递归解法

前序

public static void preOrderIteration(TreeNode head) {if (head == null) {return;}Stack<TreeNode> stack = new Stack<>();stack.push(head);while (!stack.isEmpty()) {TreeNode node = stack.pop();System.out.print(node.value + " ");if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}
}

中序

public static void inOrderIteration(TreeNode head) {if (head == null) {return;}TreeNode cur = head;Stack<TreeNode> stack = new Stack<>();while (!stack.isEmpty() || cur != null) {while (cur != null) {stack.push(cur);cur = cur.left;}TreeNode node = stack.pop();System.out.print(node.value + " ");if (node.right != null) {cur = node.right;}}
}

后序

public static void postOrderIteration(TreeNode head) {if (head == null) {return;}Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();stack1.push(head);while (!stack1.isEmpty()) {TreeNode node = stack1.pop();stack2.push(node);if (node.left != null) {stack1.push(node.left);}if (node.right != null) {stack1.push(node.right);}}while (!stack2.isEmpty()) {System.out.print(stack2.pop().value + " ");}}