投稿
  1. 极客之音首页
  2. 技术随笔

面试之算法：二叉树遍历、左/右叶子节点和、构建二叉树、最大深度、是否平衡、将有序数组转换为二叉树、二叉树求和路径、右视图、序列化、反序列化(Java)

飞熊 • • 技术随笔 • 阅读 216

勤奋不是嘴上说说而已，而是实际的行动，在勤奋的苦度中持之以恒，永不退却。业精于勤，荒于嬉；行成于思，毁于随。在人生的仕途上，我们毫不迟疑地选择勤奋，她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考，拥着勤奋的手去耕耘，用抱勤奋的心去对待工作，浪迹红尘而坚韧不拔，那么，我们的生命就会绽放火花，让人生的时光更加的闪亮而精彩。

导读：本篇文章讲解 面试之算法：二叉树遍历、左/右叶子节点和、构建二叉树、最大深度、是否平衡、将有序数组转换为二叉树、二叉树求和路径、右视图、序列化、反序列化(Java)，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com，来源：原文

概述

二叉树的定义：

private static class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private final int val;

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

遍历

二叉树的遍历方式有很多，

层序遍历

后序遍历+迭代

public static List<Integer> postOrderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> nodeStack = new Stack<>();
    TreeNode nodeTemp = root;
    TreeNode preNode = null;
    while (nodeTemp != null || !nodeStack.isEmpty()) {
        while (nodeTemp != null) {
            nodeStack.push(nodeTemp);
            nodeTemp = nodeTemp.left;
        }
        nodeTemp = nodeStack.peek();
        if (nodeTemp.right == null || nodeTemp.right == preNode) {
            nodeTemp = nodeStack.pop();
            list.add(nodeTemp.val);
            preNode = nodeTemp;
            nodeTemp = null;
        } else {
            nodeTemp = nodeTemp.right;
        }
    }
    return list;
}

求一棵树所有左叶子节点的和

左叶子的定义，递归找到所有的子树的左叶子节点。

如果二叉树的左子树是叶子节点，要找的就是它。
如果二叉树的左子树不是一个叶子节点，则递归调用此过程去获取左子树的左叶子节点的值。
二叉树的右子树，递归调用获取右子树的左叶子节点值即可。

public class SumOfLeftLeaves {
    /**
     * 递归方式
     */
    public static int sumOfLeftLeaves(TreeNode root) {
        // 递归结束条件
        if (root == null) {
            return 0;
        }
        int left, right;
        if (root.left != null && root.left.left == null && root.left.right == null) {
            // 判断是否为左叶子节点
            left = root.left.val;
        } else {
            left = sumOfLeftLeaves(root.left);
        }
        right = sumOfLeftLeaves(root.right);
        return left + right;
    }

    /**
     * 前序遍历迭代方式
     */
    public static int sumOfLeftLeavesByPreOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        int sum = 0;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                if (root.left != null && root.left.left == null && root.left.right == null) {
                    sum += root.left.val;
                }
                root = root.left;
            }
            if (!stack.isEmpty()) {
                root = stack.pop().right;
            }
        }
        return sum;
    }

    /**
     * 层级遍历二叉树,层序遍历,广度遍历
     */
    public static int sumOfLeftLeavesByLevelOrder(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        int sum = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null && node.left.left == null && node.left.right == null) {
                sum += node.left.val;
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return sum;
    }

    /**
     * 层次遍历
     */
    public static void levelOrderTraversal(TreeNode node) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
}

从中序与后序遍历序列构造二叉树

public static TreeNode buildTree(int[] inOrder, int[] postOrder) {
    return helper(inOrder, postOrder, postOrder.length - 1, 0, inOrder.length - 1);
}

private static TreeNode helper(int[] inOrder, int[] postOrder, int postEnd, int inStart, int inEnd) {
    if (inStart > inEnd) {
        return null;
    }
    int currentVal = postOrder[postEnd];
    TreeNode current = new TreeNode(currentVal);
    int inIndex = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inOrder[i] == currentVal) {
            inIndex = i;
        }
    }
    TreeNode left = helper(inOrder, postOrder, postEnd - (inEnd - inIndex) - 1, inStart, inIndex - 1);
    TreeNode right = helper(inOrder, postOrder, postEnd - 1, inIndex + 1, inEnd);
    current.left = left;
    current.right = right;
    return current;
}

二叉树最大深度

也叫最大高度；思路：分别求出左右子树的最大深度，然后取其较大者。

public static int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int deep = 1;
    if (root.left == null && root.right == null) {
        return 1;
    }
    int leftDeep = 0;
    if (root.left != null) {
        leftDeep = 1 + maxDepth(root.left);
    }
    int rightDeep = 0;
    if (root.right != null) {
        rightDeep = 1 + maxDepth(root.right);
    }
    return deep + leftDeep > rightDeep ? leftDeep : rightDeep;
}

简化版：

public static int maxDepth1(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 注意要+1
    return Math.max(maxDepth1(root.left), maxDepth1(root.right)) + 1;
}

平衡二叉树

判断给定的二叉树是否是一颗平衡树。平衡树的定义是左右子树的高度差不超过1。

public static boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    return (Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1) && isBalanced(root.left)
            && isBalanced(root.right);
}

将有序数组转换为二叉搜索树

给定一个升序排序的整数数组 nums，将其转换为一棵高度平衡的二叉搜索树。
分析：给定一个有序数组，转换成二叉搜索树，即左子树小于根节点，根节点小于右子树，满足条件的二叉搜索树显然不止一种。

public static TreeNode sortedArrayToBST(int[] nums) {
    return traversal(nums, 0, nums.length - 1);
}
public static TreeNode traversal(int[] nums, int left, int right) {
    if (left > right){
        return null;
    }
    int mid = left + ((right - left) / 2);
    TreeNode node = new TreeNode(nums[mid]);
    node.left = traversal(nums, left, mid - 1);
    node.right = traversal(nums, mid + 1, right);
    return node;
}

二叉树求和路径

给定一个二叉树，和一个整数sum，求路径和为sum的方案。

分析：路径指的是从根节点到叶子节点，每次可以选择左子树或右子树。假如sum过小或过大，则不存在这样的路径；有时，存在不止一条路径。

public static List<List<Integer>> pathSum(TreeNode root, int sum) {
    if (root == null) {
        return new ArrayList<>();
    }
    List<List<Integer>> ans = new ArrayList<>();
    if (root.val == sum && root.left == null && root.right == null) {
        List<Integer> arr = new ArrayList<>();
        arr.add(root.val);
        ans.add(arr);
        return ans;
    }
    List<List<Integer>> left = pathSum(root.left, sum - root.val);
    List<List<Integer>> right = pathSum(root.right, sum - root.val);
    for (List<Integer> list : left) {
        list.add(0, root.val);
        ans.add(list);
    }
    for (List<Integer> list : right) {
        list.add(0, root.val);
        ans.add(list);
    }
    return ans;
}

二叉树中的最大路径和

二叉树的右视图

右视图的定义：从右侧看一棵树，从上到下看到的右叶子节点序列。

public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        list.add(root.val);
        List<Integer> list1 = rightSideView(root.right);
        List<Integer> list2 = rightSideView(root.left);
        list.addAll(list1);
        if (list1.size() < list2.size()) {
            for (int i = list1.size(); i < list2.size(); i++) {
                list.add(list2.get(i));
            }
        }
        return list;
    }

序列化

思路和层序遍历没有多大差别：

public static String serialize(TreeNode root) {
    if (root == null) {
        return "[]";
    }
    ArrayList<TreeNode> queue = new ArrayList<>();
    queue.add(root);
    for (int i = 0; i < queue.size(); i++) {
        TreeNode node = queue.get(i);
        if (node == null) {
            continue;
        }
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    while (queue.get(queue.size() - 1) == null) {
        queue.remove(queue.size() - 1);
    }
    StringBuilder sb = new StringBuilder();
    sb.append("[");
    sb.append(queue.get(0));
    for (int i = 1; i < queue.size(); i++) {
        if (queue.get(i) == null) {
            sb.append(",");
            sb.append("null");
        } else {
            sb.append(",");
            sb.append(queue.get(i).val);
        }
    }
    sb.append("]");
    return sb.toString();
}

反序列化

拓展

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/142084.html

赞 (0)
飞熊的头像飞熊bm
0 0

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！