二叉树的递归遍历|前中后序遍历、最大深度、最大直径

本文主要是介绍二叉树的递归遍历|前中后序遍历、最大深度、最大直径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树的递归遍历

前序遍历

    public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}res.add(root.val);if (root.left != null) {res.addAll(preorderTraversal(root.left));}if (root.right != null) {res.addAll(preorderTraversal(root.right));}return res;}

中序遍历

    public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}if (root.left != null) {res.addAll(inorderTraversal(root.left));}res.add(root.val);if (root.right != null) {res.addAll(inorderTraversal(root.right));}return res;}

后序遍历

    public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}if (root.left != null) {res.addAll(postorderTraversal(root.left));}if (root.right != null) {res.addAll(postorderTraversal(root.right));}res.add(root.val);return res;}

层序遍历

    List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {if (root == null) {return res;}helper(root, 0);return res;}private void helper(TreeNode root, int level) {if (level == res.size()) {res.add(new ArrayList<>());}res.get(level).add(root.val);if (root.left != null) {helper(root.left, level+1);}if (root.right != null) {helper(root.right, level+1);}}

最大深度

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

最大直径

    int maxd = 0;public int diameterOfBinaryTree(TreeNode root) {if (root == null) {return 0;}depth(root);return maxd;}private int depth(TreeNode root) {if (root == null) {return 0;}int left = depth(root.left);int right = depth(root.right);maxd = Math.max(left+right, maxd); //获得当前节点的直径为 左右子树深度和return Math.max(left, right) + 1; //当前节点的深度为左右子树深度的最大值+1}

这篇关于二叉树的递归遍历|前中后序遍历、最大深度、最大直径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---