二叉树算法

二叉树遍历

递归

前序遍历

中序遍历

后序遍历

迭代

前序遍历二叉树前序遍历迭代法（显示递归栈）结果放到数组中，不停的往后放

中序遍历

后续遍历

二叉树后序遍历迭代法（显示递归栈）前序遍历结果放到ArrayList数组中，不停的往后放, 后序遍历结果放到LinkedList(双端队列，可以往前放)中，结果不停的往前放。与前序历不同之处：

把左右节点的入栈顺序调换
完成整个数组的反转（通过linkedList双端队列完成）如果不用LinkedList把结果放在前面则可以用Collections把结果反转

统一迭代

前序遍历

中序遍历

后序遍历

层序遍历

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();  //固定大小的size
            List<Integer> list = new ArrayList<>();
            for(int i = 0;i < size; i++){
                TreeNode node = queue.peek();  //获取队列第一个元素
                queue.poll();                  //删除队列的第一个元素
                list.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(list);
        }
        return res;
    }
}

剑指 Offer 07. 重建二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0) return null;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            hashMap.put(inorder[i], i);
        }
        return dfs(preorder, 0 , inorder.length - 1, 0 ,hashMap);
    }
    public TreeNode dfs(int[] preorder, int pl, int pr, int il, HashMap<Integer, Integer> hashMap){
        if(pl > pr) return null;
        TreeNode curRoot = new TreeNode(preorder[pl]);
        int k = hashMap.get(curRoot.val);
        curRoot.left  = dfs(preorder, pl + 1, pl + (k - il), il, hashMap);
        curRoot.right = dfs(preorder, pl + (k - il) + 1, pr, k + 1, hashMap);
        return curRoot;
    }
}

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构，即 A中有出现和B相同的结构和节点值

剑指 Offer 27. 二叉树的镜像

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return null;
        }
        swap(root);
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
    private void swap(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

剑指 Offer 28. 对称的二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return dfs(root, root);
    }
    public boolean dfs(TreeNode p, TreeNode q){
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        return dfs(p.left, q.right) && dfs(p.right, q.left);
    }
}

剑指 Offer 32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null){
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> arr = new ArrayList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            arr.add(node.val);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
        int[] res = new int[arr.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = arr.get(i);
        }
        return res;
    }
}

剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null){
            queue.add(root);
        }
        while(!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.peek();
                queue.poll();
                list.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(list);
        }
        return res;
    }
}

剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null){
            queue.add(root);
        }
        while(!queue.isEmpty()){
            int size = queue.size();
            LinkedList<Integer> list = new LinkedList<>();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0){
                    list.addLast(node.val);
                }else{
                    list.addFirst(node.val);
                }
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(list);
        }
        return res;
    }
}

剑指 Offer 33. 二叉搜索树的后序遍历序列

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return res(postorder, 0 , postorder.length - 1);
    }
    private boolean res(int[] postorder, int i, int j){
        if(i >= j){
            return true;
        }
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p==j&&res(postorder, i , m-1)&&res(postorder, m ,j-1);
    }
}

剑指 Offer 34. 二叉树中和为某一值的路径

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        res(root, target);
        return res;
    }
    public void res(TreeNode root, int target){
        if(root == null){
            return;
        }
        path.add(root.val);
        target = target - root.val;
        if(target == 0 && root.left== null && root.right==null){
            res.add(new LinkedList(path));
        }
        res(root.left, target);
        res(root.right, target);
        path.removeLast();
    }
}

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    Node head, pre;
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        dfs(root);
        pre.right = head;
        head.left =pre;//进行头节点和尾节点的相互指向，这两句的顺序也是可以颠倒的
        return head;
    }
    public void dfs(Node cur){
        if(cur==null) return;
        dfs(cur.left);
        //pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur,
        //当pre==null时，cur左侧没有节点,即此时cur为双向链表中的头节点
        if(pre==null) head = cur;
        //反之，pre!=null时，cur左侧存在节点pre，需要进行pre.right=cur的操作。
        else pre.right = cur;
        cur.left = pre;//pre是否为null对这句没有影响,且这句放在上面两句if else之前也是可以的。
        pre = cur;//pre指向当前的cur
        dfs(cur.right);//全部迭代完成后，pre指向双向链表中的尾节点
    }
}

剑指 Offer 37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode t = q.poll();
            if(t != null){
                res.append(t.val + ",");
                q.add(t.left);
                q.add(t.right);
            }else{
                res.append("null,");
            }
        }
        res.append("]");
        return res.toString();
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(!vals[i].equals("null")){
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                q.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")){
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                q.add(node.right);
            }
            i++;
        }
        return root;
    }
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int k1, res;
    public int kthLargest(TreeNode root, int k) {
        k1 = k;
        dfs(root);
        return res;
    }
    private void dfs(TreeNode root){
        if(root == null || k1 == 0){
            return;
        }
        dfs(root.right);  //右子树
        if(--k1 == 0) res = root.val;  //根节点
        dfs(root.left);   //左子树
    }
}

剑指 Offer 55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 //左右子树的最大深度，再加上根节点的深度1,一起构成树的深度
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return left > right ? left + 1 : right + 1;
    }
}

剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int left = treeDepth(root.left);
        int right = treeDepth(root.right);   //任意节点都满足
        return Math.abs(left - right) > 1 ? false : true && isBalanced(root.left) &&
        isBalanced(root.right);
    }
    //树的深度
    public int treeDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int a = treeDepth(root.left);
        int b = treeDepth(root.right);
        return a > b ? a + 1:b + 1;
    }
}

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val > q.val){
            TreeNode temp = p;
            p = q;
            q = temp;
        }
        while(root != null){
            if(root.val < p.val){
                root = root.right;
            }else if(root.val > q.val){
                root = root.left;
            }else{
                break;
            }
        }
        return root;
    }
}
class Solution{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        return root;
    }
}

剑指 Offer 68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

数据结构与算法

二叉树遍历

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

102. 二叉树的层序遍历

递归

迭代

统一迭代

层序遍历

剑指 Offer 07. 重建二叉树

剑指 Offer 26. 树的子结构

剑指 Offer 27. 二叉树的镜像

剑指 Offer 28. 对称的二叉树

剑指 Offer 32 - I. 从上到下打印二叉树

剑指 Offer 32 - II. 从上到下打印二叉树 II

剑指 Offer 32 - III. 从上到下打印二叉树 III

剑指 Offer 33. 二叉搜索树的后序遍历序列

剑指 Offer 34. 二叉树中和为某一值的路径

剑指 Offer 36. 二叉搜索树与双向链表

剑指 Offer 37. 序列化二叉树

剑指 Offer 54. 二叉搜索树的第k大节点

剑指 Offer 55 - I. 二叉树的深度

剑指 Offer 55 - II. 平衡二叉树

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先