算法-二叉树-1

先序遍历非递归写法

1. 先入栈弹出打印

2. 然后先压入右节点再压入左节点

3. 重复

 1 public void printPre(TreeNode node) {
 2         Stack<TreeNode> stack = new Stack<>();
 3         stack.push(node);
 4         while (!stack.isEmpty()) {
 5             TreeNode pop = stack.pop();
 6             System.out.println(pop.value);
 7             if (pop.right != null) {
 8                 stack.push(pop.right);
 9             }
10             if (pop.left != null) {
11                 stack.push(pop.left);
12             }
13 
14         }
15     }

中序遍历非递归写法

1. 先入栈所有的左子节点

2. 弹出节点输出并压入弹出节点的右节点的左子节点

 1 public void printMid(TreeNode node) {
 2         Stack<TreeNode> stack = new Stack<>();
 3         while (node != null || !stack.isEmpty()) {
 4             if (node != null) {
 5                 stack.push(node);
 6                 node = node.left;
 7             } else {
 8                 TreeNode pop = stack.pop();
 9                 System.out.println(pop.value);
10                 node = pop.right;
11             }
12         }
13 
14     }

后序遍历非递归写法

1. 两个栈stack/result

2. 头节点先压入stack栈

3. 弹出放入result栈

4. stack栈压入stack弹出节点的左子节点右子节点

5. 直到stack为空依次弹出result为后序

 1  public void printAfter(TreeNode node){
 2         Stack<TreeNode> stack = new Stack<>();
 3         Stack<TreeNode> result = new Stack<>();
 4         stack.push(node);
 5         while (!stack.isEmpty()){
 6             TreeNode pop = stack.pop();
 7             result.push(pop);
 8             if (pop.left != null){
 9                 stack.push(pop.left);
10             }
11             if (pop.right != null){
12                 stack.push(pop.right);
13             }
14         }
15         while (!result.isEmpty()){
16             TreeNode pop = result.pop();
17             System.out.print(pop.value+" ");
18         }
19 
20     }

宽度优先遍历

使用一个队列,先放入头节点弹出打印然后先放左后放右

 1  public int width(TreeNode node){
 2         Queue<TreeNode> queue = new LinkedList<>();
 3         queue.offer(node);
 4         TreeNode nodeCurEnd = node;
 5         TreeNode nextEnd = null;
 6         int max = Integer.MIN_VALUE;
 7         int curLevelNodes = 0;
 8         while (!queue.isEmpty()){
 9             TreeNode poll = queue.poll();
10             curLevelNodes++;
11             if (poll.left != null){
12                 queue.offer(poll.left);
13                 nextEnd = poll.left;
14             }
15             if (poll.right != null){
16                 queue.offer(poll.right);
17                 nextEnd = poll.right;
18             }
19             if (poll == nodeCurEnd){
20                 max = Math.max(max,curLevelNodes);
21                 curLevelNodes = 0;
22                 nodeCurEnd = nextEnd;
23             }
24         }
25         return Math.max(max,curLevelNodes);
26     }

算法题:

1. 判断是否是搜索二叉树

　　中序遍历有序才是搜索二叉树

2. 判断是否是完全二叉树

　　宽度遍历满足两个条件,1. 不能只有右孩子没有左孩子节点 2. 当第一次出现叶子节点的时候后面的节点必须都是叶子节点

3. 判断是否是满二叉树

　　1. 满二叉树节点个数 = 2 * 最大深度 -1

4. 判断是否是平衡二叉树

　　对于任何子树来说左数的高度与右树的高度相差不超过1

　　左子树与右子树都是平衡树

二叉树算法套路

创建一个对象用于存储需要的数据

左子树返回结果

右子树返回结果

组合结果然后返回