赞
踩
目录
- public void preOrder(TreeNode root) {
- // 1. 如果是一棵空树,就直接返回
- if (root == null) {
- return;
- }
- // 2. 处理根节点
- System.out.print(root.value + " ");
- // 3. 处理左子树
- preOrder(root.left);
- // 4. 处理右子树
- preOrder(root.right);
- }
- */
- public void inOrder(TreeNode root) {
- // 1. 如果是一棵空树,就直接返回
- if (root == null) {
- return;
- }
- // 2.先处理左子树
- inOrder(root.left);
- // 3.处理根节点,打印操作
- System.out.print(root.value + " ");
- // 4. 处理右子树
- inOrder(root.right);
- }
- public void postOrder(TreeNode root) {
- // 1. 如果是一棵空树,就直接返回
- if (root == null) {
- return;
- }
- // 2. 处理左子树
- postOrder(root.left);
- // 3. 处理右子树
- postOrder(root.right);
- // 4. 处理根节点,打印操作
- System.out.print(root.value + " ");
- }
- public List<Integer> preorder(TreeNode root) {
- // 1.先定义一个这棵树节点的集合
- List<Integer> list = new ArrayList<>();
- if (root == null) {
- return list;
- }
- // 2. 现在是前序遍历规则,先把根节点的值,加入到集合
- list.add(root.value);
- // 3. 处理左子树
- List<Integer> leftList = preorder(root.left);
- // 4. 把左子树的集合合并到当前整棵树的集合中
- list.addAll(leftList);
- // 5. 处理右子树
- List<Integer> rightList = preorder(root.right);
- // 6. 把右子树的集合合并到当前整棵树的集合中
- list.addAll(rightList);
- // 7. 返回最终的结果集合
- return list;
- }
- public List<Integer> inorder(TreeNode root) {
- // 1.先定义一个这棵树节点的集合
- List<Integer> list = new ArrayList<>();
- if (root == null) {
- return list;
- }
- // 2. 处理左子树
- List<Integer> leftList = inorder(root.left);
- // 3. 把左子树的集合合并到当前整棵树的集合中
- list.addAll(leftList);
- //4. 现在是中序遍历规则,把根节点的值,加入到集合
- list.add(root.value);
- // 5. 处理右子树
- List<Integer> rightList = inorder(root.right);
- // 6. 把右子树的集合合并到当前整棵树的集合中
- list.addAll(rightList);
- // 7. 返回最终的结果集合
- return list;
- }
- public void postOrder(TreeNode root) {
- // 1.先定义一个这棵树节点的集合
- List<Integer> list = new ArrayList<>();
- if (root == null) {
- return list;
- }
- // 2. 处理左子树
- List<Integer> leftList = postorder(root.left);
- // 3. 把左子树的集合合并到当前整棵树的集合中
- list.addAll(leftList);
- // 5. 处理右子树
- List<Integer> rightList = postorder(root.right);
- // 6. 把右子树的集合合并到当前整棵树的集合中
- list.addAll(rightList);
- //7. 现在是后序遍历规则,最后把根节点的值,加入到集合
- list.add(root.value);
- // 8. 返回最终的结果集合
- return list;
- }
-
- public List<Integer> preorderTraversal(TreeNode root) {
- List<Integer> list=new ArrayList<>();
- Stack<TreeNode> stack=new Stack<>();
- if(root==null){
- return list;
- }
- stack.push(root);
- while(!stack.isEmpty()){
- TreeNode tmp=stack.pop();
- if(tmp.right!=null){
- stack.push(tmp.right);
- }
- //利用栈的特性,先把右节点压入栈底,保证左节点始终先出栈
- if(tmp.left!=null){
- stack.push(tmp.left);
-
- }
- list.add(tmp.val);
- }
-
- return list;
- }
-
- public List<Integer> inorderTraversal(TreeNode root) {
- List<Integer> list=new ArrayList<>();
- Stack<TreeNode> stack=new Stack<>();
- if(root==null){
- return list;
- }
- while(root!=null||!stack.isEmpty()){
-
- while(root!=null){
- stack.push(root);
- root=root.left;
- }
- TreeNode tmp=stack.pop();
- list.add(tmp.val);
- root=tmp.right;
- }
- return list;
-
- }
- public List<Integer> postorderTraversal(TreeNode root) {
- List<Integer> list=new ArrayList<>();
- //使用两个栈
- Stack<TreeNode> stack1=new Stack<>();
- Stack<TreeNode> stack2=new Stack<>();
- if(root==null){
- return list;
- }
- stack1.push(root);
- while(!stack1.isEmpty()){
- TreeNode tmp=stack1.pop();
- stack2.push(tmp);
- if(tmp.left!=null){
- stack1.push(tmp.left);
- }
- if(tmp.right!=null){
- stack1.push(tmp.right);
- }
- }
- while(!stack2.isEmpty()){
- list.add(stack2.pop().val);
- }
- return list;
- }
- public List<List<Integer>> levelOrder(TreeNode root) {
- List<List<Integer>> list1=new ArrayList<>();
- if(root==null){
- return list1;
- }
- Queue<TreeNode> queue=new LinkedList<>();
- queue.offer(root);
- while(!queue.isEmpty()){
- int size=queue.size();
- List<Integer> list2=new ArrayList<>();
- for(int i=1;i<=size;i++){
- //出队列
- TreeNode tmp=queue.poll();
- if(tmp.left!=null){
- queue.offer(tmp.left);
- }
- if(tmp.right!=null){
- queue.offer(tmp.right);
- }
- list2.add(tmp.val);
- }
- list1.add(list2);
- }
- return list1;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。