沙河高端网站建设,建立网站的几个步骤,百度推广广告公司,网络营销期末考试题库二叉树的中序遍历
给定一个二叉树的根节点 root #xff0c;返回 它的 中序 遍历 。
示例 1#xff1a; 输入#xff1a;root [1,null,2,3] 输出#xff1a;[1,3,2]
解题思路
中序遍历是一种二叉树遍历方式#xff0c;按照“左根右”的顺序遍历二叉树节点。
1、递归…二叉树的中序遍历
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。
示例 1 输入root [1,null,2,3] 输出[1,3,2]
解题思路
中序遍历是一种二叉树遍历方式按照“左根右”的顺序遍历二叉树节点。
1、递归地遍历左子树。2、访问当前节点。3、递归地遍历右子树。
对应先序遍历 根左右 对应后序遍历 左右根
先、中、后序遍历其实指的是遍历根节点的先后顺序
Java实现中序遍历
public class InorderTraversal {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val val;}}public ListInteger inorderTraversal(TreeNode root) {ListInteger result new ArrayList();inorderTraversalHelper(root, result);return result;}private void inorderTraversalHelper(TreeNode node, ListInteger result) {if (node null) {return;}inorderTraversalHelper(node.left, result);result.add(node.val);inorderTraversalHelper(node.right, result);}public static void main(String[] args) {// 示例用法TreeNode root new TreeNode(1);root.left new TreeNode(4);root.right new TreeNode(2);root.right.left new TreeNode(3);InorderTraversal solution new InorderTraversal();ListInteger result solution.inorderTraversal(root);System.out.println(result); // 输出[4, 1, 3, 2]}
}
Java实现先序遍历
/*** 先序遍历* 根-左-右*/
public class PreorderTraversal {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val val;}}public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();preorderTraversalHelper(root, result);return result;}private void preorderTraversalHelper(TreeNode node, ListInteger result) {if (node null) {return;}result.add(node.val);preorderTraversalHelper(node.left,result);preorderTraversalHelper(node.right,result);}public static void main(String[] args) {// 示例用法TreeNode root new TreeNode(1);root.left new TreeNode(4);root.left.left new TreeNode(5);root.left.left.right new TreeNode(8);root.left.right new TreeNode(6);root.right new TreeNode(2);root.right.left new TreeNode(3);PreorderTraversal solution new PreorderTraversal();ListInteger result solution.preorderTraversal(root);System.out.println(result); // 输出[1, 3, 2]}
}
Java实现后序遍历
/*** 后序遍历* 左-右-根*/
public class PostorderTraversal {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val val;}}public ListInteger postorderTraversal(TreeNode root) {ListInteger result new ArrayList();postorderTraversalHelper(root, result);return result;}private void postorderTraversalHelper(TreeNode node, ListInteger result) {if (node null) {return;}postorderTraversalHelper(node.left, result);postorderTraversalHelper(node.right, result);result.add(node.val);}public static void main(String[] args) {// 示例用法TreeNode root new TreeNode(1);root.left new TreeNode(4);root.right new TreeNode(2);root.right.left new TreeNode(3);PostorderTraversal solution new PostorderTraversal();ListInteger result solution.postorderTraversal(root);System.out.println(result); // 输出[1, 3, 2]}
}
时间空间复杂度
时间复杂度O(n)其中n是二叉树中的节点数每个节点都需要访问一次。空间复杂度O(n)取决于递归调用栈的深度最坏情况下为O(n)。
