牛客网算法——名企高频面试题143题（15)

二叉树的遍历三种的使用的栈的遍历

package 复现代码;

import org.junit.Test;

import java.util.*;

/**
 * @Classname 二叉树的遍历
 * @Description TODO
 * @Date 2020/12/23 10:35
 * @Created by xjl
 */
public class 二叉树的遍历 {
    /**
     * @description TODO  树节点的定义
     * @param: null
     * @date: 2020/12/23 10:36
     * @return:
     * @author: xjl
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * @description TODO  前序遍历 根左右  采用的递归的调用的方式
     * @param: root
     * @date: 2020/12/23 10:37
     * @return: java.util.List
     * @author: xjl
     */
    public List before(TreeNode root) {
        ArrayList ans = new ArrayList();
        beforeserch(root, ans);
        return ans;
    }

    /**
     * @description TODO  采用的是递归的这样的一种方式
     * @param: root
     * @param: ans
     * @date: 2020/12/23 10:41
     * @return: void
     * @author: xjl
     */
    private void beforeserch(TreeNode root, ArrayList ans) {
        if (root == null) {
            return;
        }
        ans.add(root.val);
        if (root.left != null) {
            beforeserch(root.left, ans);
        }
        if (root.right != null) {
            beforeserch(root.right, ans);
        }
    }

    /**
     * @description TODO  需要采用的是的非递归的一种方式的
     * @param: root
     * @param: ans
     * @date: 2020/12/23 10:45
     * @return: void
     * @author: xjl
     */
    private List beforeserch1(TreeNode root) {
        List res = new ArrayList();
        //栈 用于存放树节点
        Deque stack = new ArrayDeque();

        while (root != null || !stack.isEmpty()) {
            //go left down to the ground
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.left;
            }
            //if we reach to the leaf, go back to the parent right, and repeat the go left down.
            TreeNode cur = stack.pop();
            root = cur.right;
        }
        return res;
    }

    /**
     * @description TODO 后序完整代码  左右根
     * @param: root
     * @date: 2020/12/23 12:59
     * @return: java.util.List
     * @author: xjl
     */
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Deque stack = new ArrayDeque();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.right;
            }

            TreeNode cur = stack.pop();
            root = cur.left;
        }
        //相当于是的反转前序遍历问题
        Collections.reverse(res);
        return res;
    }

    /**
     * @description TODO  中序完整代码  左根右
     * @param: root
     * @date: 2020/12/23 12:59
     * @return: java.util.List
     * @author: xjl
     */
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Stack stack = new Stack();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(6);
        TreeNode node6 = new TreeNode(7);

        root.left = node1;
        root.right = node2;

        node1.left = node3;
        node1.right = node4;

        node2.left = node5;
        node2.left = node6;

        before(root);

    }
}

二叉树的之字形层序遍历

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList
     */
    public ArrayList zigzagLevelOrder (TreeNode root) {
        ArrayList ans = new ArrayList();
        Queue queue = new LinkedList();
        if (root == null) {
            return ans;
        }
        queue.add(root);
        //保存每一层的节点的数量个数
        int sum = 1;
        //用来控制左边还是右边的输入的
        int num = 1;

        while (!queue.isEmpty()) {
            ArrayList list = new ArrayList();
            int temp = 0;//保存当前层的下一层的节点
            while (sum > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    temp++;
                    queue.add(node.left);
                }
                if (node.right != null) {
                    temp++;
                    queue.add(node.right);
                }
                sum--;
            }
            sum = temp;
            //如果是的等于偶数的话那就是的需要将数据的翻转过来的
            if (num % 2 == 0) {
                for (int i = 0, j = list.size() - 1; i < j; i++, j--) {
                    int res = list.get(i);
                    list.set(i, list.get(j));
                    list.set(j, res);
                }
            }
            num++;
            ans.add(list);
        }
        return ans;
    }
}

平衡二叉树

package 复现代码;

/**
 * @Classname 是否为平衡树
 * @Description TODO
 * @Date 2020/12/23 13:12
 * @Created by xjl
 */
public class 是否为平衡树 {

    /**
     * @description TODO  树节点的定义
     * @param: null
     * @date: 2020/12/23 10:36
     * @return:
     * @author: xjl
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public boolean IsBalanced_Solution(TreeNode root) {
        return test(root) != -1;
    }

    private int test(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = test(root.left);
        if (left == -1) {
            return -1;
        }
        int right = test(root.right);
        if (right == -1) {
            return -1;
        }
        return Math.abs(left - right) >= 2 ? -1 : Math.max(left, right) + 1;
    }
}

层序遍历

package 复现代码;

import java.util.*;

/**
 * @Classname 二叉树的层序遍历
 * @Description TODO
 * @Date 2020/12/23 10:44
 * @Created by xjl
 */
public class 二叉树的层序遍历 {

    /**
     * @description TODO  树节点的定义
     * @param: null
     * @date: 2020/12/23 10:36
     * @return:
     * @author: xjl
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public ArrayList cengxu(TreeNode root) {
        if (root == null) {
            return new ArrayList();
        }
        ArrayList lists = new ArrayList();
        Deque deque = new LinkedList();
        deque.add(root);
        int sum = 1;
        while (!deque.isEmpty()) {
            ArrayList list = new ArrayList();
            int temp = 0;
            while (sum > 0) {
                TreeNode node1 = deque.poll();
                list.add(node1.val);
                if (node1.left != null) {
                    temp++;
                    deque.add(node1.left);
                }
                if (node1.right != null) {
                    temp++;
                    deque.add(node1.right);
                }
                sum--;
            }
            sum = temp;
            lists.add(list);
        }
        return lists;
    }

    public ArrayList cengxu2(TreeNode root) {
        if (root == null) {
            return new ArrayList();
        }

        ArrayList res = new ArrayList();
        LinkedList queue = new LinkedList();
        //将根节点放入队列中，然后不断遍历队列
        queue.add(root);
        while (!queue.isEmpty()) {
            //获取当前队列的长度，这个长度相当于 当前这一层的节点个数
            int size = queue.size();
            ArrayList tmp = new ArrayList();
            //将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
            //如果节点的左/右子树不为空，也放入队列中
            for (int i = 0; i < size; ++i) {
                TreeNode t = queue.remove();
                tmp.add(t.val);
                if (t.left != null) {
                    queue.add(t.left);
                }
                if (t.right != null) {
                    queue.add(t.right);
                }
            }
            //将临时list加入最终返回结果中
            res.add(tmp);
        }
        return res;
    }

    public List levelOrderBottom(TreeNode root) {
        if (root == null) {
            return new ArrayList();
        }
        List lists = new ArrayList();
        Deque deque = new LinkedList();
        deque.add(root);
        int sum = 1;
        while (!deque.isEmpty()) {
            ArrayList list = new ArrayList();
            int temp = 0;
            while (sum > 0) {
                TreeNode node1 = deque.poll();
                list.add(node1.val);
                if (node1.left != null) {
                    temp++;
                    deque.add(node1.left);
                }
                if (node1.right != null) {
                    temp++;
                    deque.add(node1.right);
                }
                sum--;
            }
            sum = temp;
            lists.add(list);
        }
        Collections.reverse(lists);
        return lists;
    }
}

最大的深度

package 复现代码;

/**
 * @Classname 二叉树的最大深度
 * @Description TODO
 * @Date 2020/12/23 13:30
 * @Created by xjl
 */
public class 二叉树的最大深度 {

    /**
     * @description TODO  树节点的定义
     * @param: null
     * @date: 2020/12/23 10:36
     * @return:
     * @author: xjl
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int test(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = test(root.left);
        int right = test(root.right);
        return Math.max(left, right) + 1;
    }
}

将二叉树的进行镜像

package 复现代码;

/**
 * @Classname 二叉树的镜像
 * @Description TODO
 * @Date 2020/12/23 13:35
 * @Created by xjl
 */
public class 二叉树的镜像 {

    /**
     * @description TODO  树节点的定义
     * @param: null
     * @date: 2020/12/23 10:36
     * @return:
     * @author: xjl
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public void test(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        test(root.left);
        test(root.right);
    }
}

二叉树是否对称

package 复现代码;

/**
 * @Classname 二叉树是否对称
 * @Description TODO
 * @Date 2020/12/23 13:39
 * @Created by xjl
 */
public class 二叉树是否对称 {

    /**
     * @description TODO  树节点的定义
     * @param: null
     * @date: 2020/12/23 10:36
     * @return:
     * @author: xjl
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * @description TODO  是否为对称二叉树
     * @param: root
     * @date: 2020/12/23 13:40
     * @return: boolean
     * @author: xjl
     */
    public boolean test(TreeNode root) {
        return root == null ? true : recur(root.left, root.right);
    }

    private boolean recur(TreeNode L, TreeNode R) {
        if (L == null && R == null) {
            return true;
        }
        if (L == null || R == null || L.val != R.val) {
            return false;
        }
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

是否包含子树

package 复现代码;

/**
 * @Classname 是否包含子树
 * @Description TODO
 * @Date 2020/12/12 17:36
 * @Created by xjl
 */
public class 是否包含子树 {

    public boolean isContains(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return false;
        }
        if (root2 == null) {
            return true;
        }
        return isContains(root1.left, root2) || isContains(root1.right, root2) || issameTree(root1, root2);
    }

    public boolean issameTree(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {return true;}
        if (root1 == null || root2 == null) {return false;}
        if (root1.val != root2.val) {return false;}
        return issameTree(root1.left, root2.left) && issameTree(root1.right, root2.right);
    }

    public boolean subtree(TreeNode root1, TreeNode root2) {
        if (root1 == null) {return false;}
        if (root2 == null) {return true;}
        return subtree(root1.left, root2) || subtree(root1.right, root2) || samTree(root1, root2);
    }

    private boolean samTree(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null){ return true;}
        if (root1 == null || root2 == null) {return false;}
        if (root1.val != root2.val) {return false;}
        return samTree(root1.left, root2.left) && samTree(root1.right, root2.right);
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

}