要点: 思考二叉树的题，一定要运用好遍历

例如：

对称：根左右和根右左遍历结果一样

搜索二叉树：中序遍历从小到大

1. 二叉树的遍历(前序、中序、后续、层序)

① 前序遍历

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);
    }
}
//这个代码也可以优化：在遍历的时候直接进行比较，不用存放到链表

⑥ 合并两个二叉树

合并二叉树_牛客题霸_牛客网 (nowcoder.com)

思路：还是运用递归的思路，通过前序遍历对俩树同时进行操作，要注意创建新节点的时机

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);
    }
}

二叉树 --- OJ题陪你深入理解二叉树

1. 二叉树的遍历(前序、中序、后续、层序)

① 前序遍历

② 中序遍历

③ 后序遍历

④ 层序遍历

2. 进阶题

① 之字形打印

② 求最大深度

③ 某一路径的和为某一值

④ 二叉搜索树转换成双向链表

⑤ 判断二叉树是否对称

⑥ 合并两个二叉树

⑦ 二叉树的镜像

热门文章

最新文章

相关电子书

二叉树 --- OJ题陪你深入理解二叉树

1. 二叉树的遍历(前序、中序、后续、层序)

① 前序遍历

② 中序遍历

③ 后序遍历

④ 层序遍历

2. 进阶题

① 之 字形打印

② 求最大深度

③ 某一路径的和为某一值

④ 二叉搜索树 转换成 双向链表

⑤ 判断二叉树是否对称

⑥ 合并两个二叉树

⑦ 二叉树的镜像

热门文章

最新文章

相关电子书

① 之字形打印

④ 二叉搜索树转换成双向链表