目录

树的节点表现形式:

* 遍历方式:

* 1.广度优先搜索:层序遍历  1 2 3 4 7 5 6

*LeetCode:144:前序遍历:pre-order :根左右 1 2 4 7 3 5 6  

  1.递归方式:

  2.非递归方式:

* LeetCode 94:中序遍历:in-order :左根右 4 2 7 1 5 3 6

 1.递归方式:

 2.非递归方式:

*LeetCode 145:后序遍历:post-order :左右根 4 7 2 5 6 3 1

 1.递归方式:

2.非递归方式:

---

树的节点表现形式:

* 1.TreeNode 节点,用队列来层序遍历

* 2.数组表示 层序遍历直接遍历数组即可

* 遍历方式:

* 1.广度优先搜索:层序遍历  1 2 3 4 7 5 6

eg:LeetCode :102:解答https://blog.csdn.net/m0_75035023/article/details/143520669?spm=1001.2014.3001.5501

LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.val + " ");if (node.left != null)queue.offer(node.left);if (node.right != null)queue.offer(node.right);}

* 2.深度优先搜索:

          1
*       /   \
*      2     3
*     /      /
*     4  7    5  6

*LeetCode:144:前序遍历:pre-order :根左右 1 2 4 7 3 5 6  

  1.递归方式:

public static List<Integer> preorderTraversal(TreeNode root) {LinkedList<Integer> res = new LinkedList<>();if (root == null) return res;res.add(root.val);//这样是每次都新建一个list,是错误的
//        preorderTraversal(root.left);
//        preorderTraversal(root.right);res.addAll(preorderTraversal(root.left));res.addAll(preorderTraversal(root.right));return res;}

  2.非递归方式:

class Solution {public List<Integer> preorderTraversal(TreeNode root) {// LinkedList<Integer> list=new LinkedList<>();// if(root==null){//     return list;// }// list.add(root.val);// list.addAll(preorderTraversal(root.left));// list.addAll(preorderTraversal(root.right));// return list;LinkedList<TreeNode> stack =new LinkedList<>();LinkedList<Integer> list=new LinkedList<>();TreeNode curr=root;TreeNode pop=null;while(curr!=null||!stack.isEmpty()){if(curr!=null){list.add(curr.val);stack.push(curr);curr=curr.left;}else{TreeNode peek=stack.peek();if(peek.right==null){pop=stack.pop();}else{if(peek.right==pop){pop=stack.pop();}else{curr=peek.right;}}}}return list;    }
}

* LeetCode 94:中序遍历:in-order :左根右 4 2 7 1 5 3 6

 1.递归方式:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {// LinkedList<Integer> list=new LinkedList<>();// if(root==null){//     return list;// }// list.addAll(inorderTraversal(root.left));// list.add(root.val);// list.addAll(inorderTraversal(root.right));// return list;}
}

 2.非递归方式:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {LinkedList<TreeNode> stack=new LinkedList<>();LinkedList<Integer> list=new LinkedList<>();TreeNode curr=root;TreeNode pop=null;while(curr!=null||!stack.isEmpty()){if(curr!=null){stack.push(curr);curr=curr.left;}else{TreeNode peek=stack.peek();if(peek.right==null){pop=stack.pop();list.add(pop.val);}else if(peek.right==pop){pop=stack.pop();} else{list.add(peek.val);curr=peek.right;}}}return list;}
}

*LeetCode 145:后序遍历:post-order :左右根 4 7 2 5 6 3 1

 1.递归方式:

static void postOrder(TreeNode root) {if (root == null) return;postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");}

2.非递归方式:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {LinkedList<TreeNode> stack=new LinkedList<>();LinkedList<Integer> list=new LinkedList<>();TreeNode curr=root;TreeNode pop=null;while(curr!=null|!stack.isEmpty()){if(curr!=null){stack.push(curr);curr=curr.left;}else{TreeNode peek=stack.peek();if(peek.right==null){pop=stack.pop();list.add(pop.val);}else{if(peek.right==pop){pop=stack.pop();list.add(pop.val);}else{curr=peek.right;}}}}return list;}
}