备案网站域名和主机关系,网站建设 开票税率,如何做短视频自媒体赚钱,软件项目管理方法专栏#xff1a;Java数据结构秘籍 个人主页#xff1a;手握风云 目录
一、非递归实现遍历二叉树
1.1. 二叉树的前序遍历
1.2. 二叉树的中序遍历
1.3. 二叉树的后序遍历 一、非递归实现遍历二叉树
1.1. 二叉树的前序遍历 我们这里要使用栈来进行实现。我们反向思考一下为… 专栏Java数据结构秘籍 个人主页手握风云 目录
一、非递归实现遍历二叉树
1.1. 二叉树的前序遍历
1.2. 二叉树的中序遍历
1.3. 二叉树的后序遍历 一、非递归实现遍历二叉树
1.1. 二叉树的前序遍历 我们这里要使用栈来进行实现。我们反向思考一下为什么不使用队列如下图前序遍历肯定是先将根结点放进去如果是队列根结点先进先出然后怎么去遍历右子树呢就无法打印的顺序了。 我们定义一个引用cur只要cur不为null就打印值并将该元素放入栈中。当遍历到4时左子树为空返回结点4并弹出再去遍历4的右结点然后返回结点2并弹出让cur等于结点2的右子树并遍历。只要1的左子树没有遍历完1就不弹出。
public class Solution {public void preorderTraversal(TreeNode root){if(root null){return;}StackTreeNode stack new Stack();TreeNode cur root;while(cur ! null){stack.push(cur);System.out.print(cur.val );cur cur.left;}}
} 代码写到这里就会出现问题原因是当遍历到结点4的时候4的左子树为空就无法进入while循环。然后把4弹出去让curtop问题又来了如果结点4左边要是不为空又得放入栈中也需要走while循环。 我们会发现当cur走到某个结点时如果为空但栈不为空此时就可以巧妙地在while外面再加一层while循环。
while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);System.out.print(cur.val );cur cur.left;}cur stack.pop();cur cur.right;
} 完整代码实现
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}
}public class Solution {public ListInteger preorderTraversal(TreeNode root){ListInteger tree new ArrayList();if(root null){return tree;}StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {tree.add(cur.val);stack.push(cur);cur cur.left;}cur stack.pop();cur cur.right;}return tree;}
}
import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {ListInteger result new ArrayList();Solution solution new Solution();TreeNode root new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left new TreeNode(4);root.left.right new TreeNode(5);root.left.right.left new TreeNode(6);root.left.right.right new TreeNode(7);root.right.right new TreeNode(8);root.right.right.left new TreeNode(9);result solution.preorderTraversal(root);System.out.println(result);}
}
1.2. 二叉树的中序遍历 与前序遍历的思路相同只是打印的时机不一样。中序遍历要在弹出的元素之后直接打印。 完整代码实现
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}
}public class Solution {public ListInteger inorderTraversal(TreeNode root){ListInteger tree new ArrayList();if(root null){return tree;}StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {tree.add(cur.val);stack.push(cur);cur cur.left;}cur stack.pop();tree.add(cur.val);cur cur.right;}return tree;}
}import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {ListInteger result new ArrayList();Solution solution new Solution();TreeNode root new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left new TreeNode(4);root.left.right new TreeNode(5);root.left.right.left new TreeNode(6);root.left.right.right new TreeNode(7);root.right.right new TreeNode(8);root.right.right.left new TreeNode(9);result solution.inorderTraversal(root);System.out.println(result);}
}1.3. 二叉树的后序遍历 后序遍历不能按照我们上面前序与中序的方法来做。如果结点下面还有孩子结点如果把4弹出之后就无法获取它的右侧所以只能获取不能弹出。当右子树为空才能弹出再进行打印。 public class Solution {public void postorderTraversal(TreeNode root){if(root null){return;}StackTreeNode stack new Stack();TreeNode cur root;TreeNode top null;while(cur ! null || !stack.isEmpty()) {while(cur ! null){stack.push(cur);cur cur.left;}top stack.peek();if(top.right null){stack.pop();System.out.print(top.val );}else{cur top.right;}}}
}public class Test {public static void main(String[] args) {Solution solution new Solution();TreeNode root new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left new TreeNode(4);root.left.right new TreeNode(5);root.left.right.right new TreeNode(7);root.right.right new TreeNode(8);root.right.right.left new TreeNode(9);solution.postorderTraversal(root);}
}但这样写会存在问题当遍历到结点5的右结点7时会陷入死循环。那我们怎么知道这个结点被打印过我们再定义引用prev让prev来记录被弹出的结点。 while(cur ! null || !stack.isEmpty()) {while(cur ! null){stack.push(cur);cur cur.left;}top stack.peek();if(top.right null || top.right prev){stack.pop();System.out.print(top.val );prev top;}else{cur top.right;} 完整代码实现
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}
}public class Solution {public ListInteger postorderTraversal(TreeNode root){ListInteger tree new ArrayList();if(root null){return tree;}StackTreeNode stack new Stack();TreeNode cur root;TreeNode top null;TreeNode prev null;while(cur ! null || !stack.isEmpty()) {while(cur ! null){stack.push(cur);cur cur.left;}top stack.peek();if(top.right null || top.right prev){tree.add(top.val);stack.pop();prev top;}else{cur top.right;}}return tree;}
}
import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {ListInteger tree new ArrayList();Solution solution new Solution();TreeNode root new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left new TreeNode(4);root.left.right new TreeNode(5);root.left.right.left new TreeNode(6);root.left.right.right new TreeNode(7);root.right.right new TreeNode(8);root.right.right.left new TreeNode(9);tree solution.postorderTraversal(root);System.out.println(tree);}
}
