双非本科准备秋招（15.3）—— 力扣二叉树

        今天学了二叉树结点表示法，建树代码如下。

public class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}@Overridepublic String toString() {return String.valueOf(val);}
}

        我们建一棵树，然后使用递归的方式前中后序遍历（preOrder、inOrder、postOrder），再使用非递归方式遍历（traversal）。

public class Test {public static void main(String[] args) {TreeNode root = new TreeNode(1,new TreeNode(2, new TreeNode(4, null, null), null),new TreeNode(3, new TreeNode(5, null, null), new TreeNode(6, null, null)));preOrder(root);inOrder(root);postOrder(root);traversal(root);}

建的树如下：

        递归深度遍历：

/*** 前序*/public static void preOrder(TreeNode t){if(t == null) return;System.out.println(t.val);preOrder(t.left);preOrder(t.right);}/*** 中序*/public static void inOrder(TreeNode t){if(t == null) return;inOrder(t.left);System.out.println(t.val);inOrder(t.right);}/*** 后序*/public static void postOrder(TreeNode t){if(t == null) return;postOrder(t.left);postOrder(t.right);System.out.println(t.val);}

        非递归的方式

        使用以下代码可以通用前中后序的遍历。

    /*** 一套代码通用遍历，改造后序遍历*/public static void traversal(TreeNode t){LinkedList<TreeNode> stack = new LinkedList<>();TreeNode pop = null;while(t != null || !stack.isEmpty()){if(t != null){//左子树还没处理System.out.println("前序： " + t.val);stack.push(t);t = t.left;}else{TreeNode peek = stack.peek();if(peek.right == null){//右子树为空System.out.println("中序： " + peek.val);pop = stack.pop();System.out.println("后序： " + pop.val);}else if(peek.right == pop){//右子树处理完成pop = stack.pop();System.out.println("后序： " + pop.val);}else{//右子树还没处理System.out.println("中序： " + peek.val);t = peek.right;}}}}

使用以上知识解决如下题目：

1、144. 二叉树的前序遍历 

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> stack = new LinkedList<>();TreeNode pop = null;while(root != null || !stack.isEmpty()){if(root != null){list.add(root.val);stack.push(root);root = root.left;}else{TreeNode peek = stack.peek();if(peek.right == null || peek.right == pop){pop = stack.pop();}else{root = peek.right;}}}return list;}
}

2、94. 二叉树的中序遍历

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> stack = new LinkedList<>();TreeNode pop = null;while(root != null || !stack.isEmpty()){if(root != null){stack.push(root);root = root.left;}else{TreeNode peek = stack.peek();if(peek.right == null){list.add(peek.val);pop = stack.pop();}else if(peek.right == pop){pop = stack.pop();}else{list.add(peek.val);root = peek.right;}}}return list;}
}

3、145. 二叉树的后序遍历

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> stack = new LinkedList<>();TreeNode pop = null;while(root != null || !stack.isEmpty()){if(root != null){stack.push(root);root = root.left;}else{TreeNode peek = stack.peek();if(peek.right == null || peek.right == pop){pop = stack.pop();list.add(peek.val);}else{root = peek.right;}}}return list;}
}