快手秒刷自助网站,沙洋网站开发,湖州网站建设推广,如何看待百度竞价排名二叉树遍历方法总结 二叉树的遍历总体上分为深度优先遍历和广度优先遍历。常见的前中后序三种遍历方式就属于深度优先遍历#xff0c;遍历过程中是顺着一条路径一直遍历到空节点然后向上回溯继续顺着遍历上一个节点的其他方向。层序遍历属于广度优先遍历#xff0c;先遍历完同…二叉树遍历方法总结 二叉树的遍历总体上分为深度优先遍历和广度优先遍历。常见的前中后序三种遍历方式就属于深度优先遍历遍历过程中是顺着一条路径一直遍历到空节点然后向上回溯继续顺着遍历上一个节点的其他方向。层序遍历属于广度优先遍历先遍历完同一层的节点再接着遍历下一层节点。 本文主要介绍二叉树三种深度优先遍历方式的实现方式递归方式和非递归方式。 递归方式实现如下。 前序遍历-力扣144
/*** 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 ListInteger preorderTraversal(TreeNode root) {ListInteger result new LinkedList();if (root null) {return result;}preOrder(root,result);return result;}private void preOrder(TreeNode current,ListInteger result) {if (current ! null) {result.add(current.val);preOrder(current.left,result);preOrder(current.right,result);}}
}中序遍历-力扣94就是把前序中的处理节点的顺序调整一下。
private void inOrder(TreeNode current,ListInteger result) {if (current ! null) { inOrder(current.left,result);result.add(current.val);inOrder(current.right,result);}
}后序遍历-力扣145将节点处理顺序调整到最后
private void inOrder(TreeNode current,ListInteger result) {if (current ! null) { inOrder(current.left,result); inOrder(current.right,result);result.add(current.val);}
}非递归方式实现如下。 前序遍历-力扣144,利用栈保存访问过的节点每访问一个节点就处理一个。
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new LinkedList();if (root null) {return result;}DequeTreeNode stack new LinkedList();stack.push(root);while (!stack.isEmpty()) {TreeNode tempNode stack.pop();result.add(tempNode.val);if (tempNode.right ! null) {stack.push(tempNode.right);}if (tempNode.left ! null) {stack.push(tempNode.left);}}return result;}
}中序遍历-力扣94
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger result new LinkedList();if (root null) {return result;}DequeTreeNode stack new LinkedList();TreeNode current root;while (!stack.isEmpty() || current ! null) {if (current ! null) {stack.push(current);current current.left;} else {TreeNode tempNode stack.pop();result.add(tempNode.val);current tempNode.right;}}return result;}
}后序遍历-力扣145后序遍历可以当成是把前序遍历顺序改变一下从前序的中左右变成中右左然后再把结果倒置。
class Solution {//后序遍历public ListInteger postorderTraversal(TreeNode root) {ListInteger result new LinkedList();if (root null) {return result;}DequeTreeNode stack new LinkedList();stack.push(root);TreeNode cur root;while (!stack.isEmpty()) {TreeNode tempNode stack.pop();result.add(tempNode.val);if (tempNode.left ! null) {stack.push(tempNode.left);}if (tempNode.right ! null) {stack.push(tempNode.right);}}Collections.reverse(result);return result;}}
