要点: 思考二叉树的题，一定要运用好 遍历
例如：
对称：根左右 和 根右左 遍历结果一样
搜索二叉树：中序遍历 从小到大
1. 二叉树的遍历(前序、中序、后续、层序)
① 前序遍历
二叉树的前序遍历_牛客题霸_牛客网 (nowcoder.com)
import java.util.*; public class Solution { public static int index = 0; public int[] preorderTraversal (TreeNode root) { // write code here int[] ret = new int[100]; p(root, ret); int[] arr = new int[index]; for(int i =0;i<index;i++){ arr[i] = ret[i]; } return arr; } public void p(TreeNode node, int[] ret) { if (node == null) return; ret[index] = node.val; index++; p(node.left, ret); p(node.right, ret); } }
② 中序遍历
二叉树的中序遍历_牛客题霸_牛客网 (nowcoder.com)
import java.util.*; public class Solution { public static int index = 0; public int[] inorderTraversal (TreeNode root) { // write code here int[] arr = new int[1000]; i(root, arr); int[] ret = new int[index]; for(int i =0;i<index;i++){ ret[i] = arr[i]; } return ret; } public void i(TreeNode node, int[] arr) { if(node == null) return; i(node.left,arr); arr[index] = node.val; index++; i(node.right,arr); } }
③ 后序遍历
二叉树的后序遍历_牛客题霸_牛客网 (nowcoder.com)
import java.util.*; public class Solution { public static int index = 0; public int[] postorderTraversal (TreeNode root) { // write code here int[] arr = new int[100]; p(root,arr); int[] ret = new int[index]; for(int i =0;i<index;i++){ ret[i] = arr[i]; } return ret; } public void p(TreeNode node,int[] arr){ if(node == null) return; p(node.left,arr); p(node.right,arr); arr[index] = node.val; index++; } }
④ 层序遍历
求二叉树的层序遍历_牛客题霸_牛客网 (nowcoder.com)
思路：灵活运用 栈 来进行解题
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) { // write code here ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); if (root == null) return ret; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ int len = queue.size(); ArrayList<Integer> list = new ArrayList<>(); for(int i=0;i<len;i++){ TreeNode node = queue.poll(); list.add(node.val); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } ret.add(list); } return ret; } }
2. 进阶题
① 之 字形打印
按之字形顺序打印二叉树_牛客题霸_牛客网 (nowcoder.com)
思路：是层序遍历的进阶版 ，使用LinkedList进行头插和尾查的时候，要注意好顺序
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); if (pRoot == null) return ret; LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(pRoot); int flag = 1; while (!queue.isEmpty()) { ArrayList<Integer> arrayList = new ArrayList<>(); int len = queue.size(); for (int i = 0; i < len; i++) { if (flag == -1) { TreeNode node = queue.pollLast(); arrayList.add(node.val); if (node.right != null) { queue.addFirst(node.right); } if (node.left != null) { queue.addFirst(node.left); } } if (flag == 1) { TreeNode node = queue.pollFirst(); arrayList.add(node.val); if (node.left != null) { queue.addLast(node.left); } if (node.right != null) { queue.addLast(node.right); } } } ret.add(arrayList); flag *=(-1); } return ret; } }
② 求最大深度
二叉树的最大深度_牛客题霸_牛客网 (nowcoder.com)
思路：运用好递归的思想，一行代码就能解决
import java.util.*; public class Solution { public static int ret = 1; public int maxDepth (TreeNode root) { if(root == null) return 0; return Math.max(maxDepth(root.left),maxDepth(root.right))+1; } }
③ 某一路径的和为某一值
二叉树中和为某一值的路径(一)_牛客题霸_牛客网 (nowcoder.com)
思路: 同样是递归，想明白过程 代码很简单
import java.util.*; public class Solution { int flag = 0; public boolean hasPathSum (TreeNode root, int sum) { if(root == null) return false; return p(root,sum); } public boolean p(TreeNode root, int sum) { if(root == null) return false; if(root.left==null&&root.right==null){ if(sum==root.val) return true; else return false; } return p(root.left, sum - root.val) || p(root.right, sum - root.val); } }
④ 二叉搜索树 转换成 双向链表
二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
思路：使用数组，将中序遍历的结果存入数组，在改变左右的指向
import java.util.*; public class Solution { public int index = 0; public static int count = 0; public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree == null) return null; if(pRootOfTree.left == null&&pRootOfTree.right==null) return pRootOfTree; TreeNode[] arr = inorderTraversal(pRootOfTree); arr[0].right = arr[1]; arr[0].left = null; for (int i = 1; i < arr.length - 1; i++) { arr[i].left = arr[i-1]; arr[i].right = arr[i+1]; } arr[arr.length-1].left = arr[arr.length-2]; arr[arr.length-1].right = null; return arr[0]; } public TreeNode[] inorderTraversal (TreeNode root) { // write code here TreeNode[] arr = new TreeNode[1000]; i(root, arr); TreeNode[] ret = new TreeNode[index]; for (int i = 0; i < index; i++) { ret[i] = arr[i]; } return ret; } public void i(TreeNode node, TreeNode[] arr) { if (node == null) return; i(node.left, arr); arr[index] = node; index++; i(node.right, arr); } }
⑤ 判断二叉树是否对称
对称的二叉树_牛客题霸_牛客网 (nowcoder.com)
思路：前序遍历的时候我们采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没有问题，那我们是不是可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的。
import java.util.*; public class Solution { boolean isSymmetrical(TreeNode pRoot) { if (pRoot == null) return true; if (pRoot.left == null && pRoot.right != null) return false; if (pRoot.right == null && pRoot.left != null) return false; LinkedList<Integer> gzyList = new LinkedList<>(); LinkedList<Integer> gyzList = new LinkedList<>(); gzy(pRoot, gzyList); gyz(pRoot, gyzList); for (int i = 0; i < gzyList.size(); i++) { int a = gzyList.poll(); int b = gyzList.poll(); if (a != b) return false; } return true; } //根-左-右 private void gzy(TreeNode root, LinkedList<Integer> list) { if (root == null) {//必须要把null也存进去！ list.add(1001); return; } list.add(root.val); gzy(root.left, list); gzy(root.right, list); } //根-右-左 private void gyz(TreeNode root, LinkedList<Integer> list) { if (root == null) {//必须要把null也存进去！ list.add(1001); return; } list.add(root.val); gyz(root.right, list); gyz(root.left, list); } } //这个代码也可以优化：在遍历的时候直接进行比较，不用存放到链表
⑥ 合并两个二叉树
思路：还是运用递归的思路，通过前序遍历对俩树同时进行操作，要注意创建新节点的时机
import java.util.*; public class Solution { public TreeNode mergeTrees (TreeNode t1, TreeNode t2) { pre(t1, t2); return t1; } private void pre(TreeNode node1, TreeNode node2) { if (node1 != null && node2 != null) { node1.val = node1.val + node2.val; } if (node2 == null) { return; } //对左树进行操作 if (node1.left == null && node2.left != null) { node1.left = new TreeNode(0); pre(node1.left, node2.left); } else { pre(node1.left, node2.left); } //对右树进行操作 if (node1.right == null && node2.right != null) { node1.right = new TreeNode(0); pre(node1.right, node2.right); } else { pre(node1.right, node2.right); } } }
⑦ 二叉树的镜像
二叉树的镜像_牛客题霸_牛客网 (nowcoder.com)
思路：遍历的时候直接交换
import java.util.*; public class Solution { public TreeNode Mirror (TreeNode pRoot) { // write code here preExchange(pRoot); return pRoot; } private void preExchange(TreeNode root) { if (root == null) return; if (root.left == null && root.right == null) return; else {//直接进行交换 TreeNode node = root.left; root.left = root.right; root.right = node; } //根处理完 对左右子树进行处理 preExchange(root.left); preExchange(root.right); } }
