首页 > 代码库 > [Leetcode][JAVA] Binary Tree Preorder Traversal, Binary Tree Inorder Traversal, Binary Tree Postorder Traversal
[Leetcode][JAVA] Binary Tree Preorder Traversal, Binary Tree Inorder Traversal, Binary Tree Postorder Traversal
Binary Tree PreOrder Traversal:
Given a binary tree, return the preorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1 2 / 3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
不使用递归前序遍历，可以借助栈的帮助实现。对于一个特定节点，前序遍历顺序为: 根，左，右。所以入栈顺序为 右，左，根。由于根节点的遍历和展开（研究其右节点和左节点）是同时的，所以根节点出栈的同时即可加入遍历结果中，然后研究其右节点和左节点，如果不为空即可入栈。
1 public List<Integer> preorderTraversal(TreeNode root) { 2 List<Integer> ls = new ArrayList<Integer>(); 3 if(root==null) 4 return ls; 5 Stack<TreeNode> st = new Stack<TreeNode>(); 6 st.push(root); 7 8 while(!st.isEmpty()) 9 {10 TreeNode temp = st.pop();11 ls.add(temp.val);12 if(temp.right!=null)13 st.push(temp.right);14 if(temp.left!=null)15 st.push(temp.left);16 }17 return ls;18 }
Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1 2 / 3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
中序遍历比前序遍历复杂一些，主要是需要区分得到的节点是需要展开还是直接遍历。一般来说第一次访问节点则展开，并且自己重新入栈，第二次从栈中访问到则计入遍历。这里采用HashSet来判断是否已经访问过。
压栈顺序为 右， 根， 左（因为中序遍历顺序为左 根 右）
1 public List<Integer> inorderTraversal(TreeNode root) { 2 List<Integer> ls = new ArrayList<Integer>(); 3 if(root==null) 4 return ls; 5 Stack<TreeNode> st = new Stack<TreeNode>(); 6 HashSet<TreeNode> hs = new HashSet<TreeNode>(); 7 8 st.push(root); 9 while(!st.isEmpty())10 {11 TreeNode temp = st.pop();12 if(hs.contains(temp))13 {14 ls.add(temp.val);15 continue;16 }17 hs.add(temp);18 if(temp.right!=null)19 st.push(temp.right);20 st.push(temp);21 if(temp.left!=null)22 st.push(temp.left);23 }24 return ls;25 }
Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1 2 / 3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
与中序遍历一样，只不过压栈顺序为根，右，左（后序遍历顺序为左，右，根）
1 public List<Integer> postorderTraversal(TreeNode root) { 2 List<Integer> ls = new ArrayList<Integer>(); 3 if(root==null) 4 return ls; 5 Stack<TreeNode> st = new Stack<TreeNode>(); 6 HashSet<TreeNode> hs = new HashSet<TreeNode>(); 7 8 st.push(root); 9 while(!st.isEmpty())10 {11 TreeNode temp = st.pop();12 if(hs.contains(temp))13 {14 ls.add(temp.val);15 continue;16 }17 hs.add(temp);18 st.push(temp);19 if(temp.right!=null)20 st.push(temp.right);21 if(temp.left!=null)22 st.push(temp.left);23 }24 return ls;25 }
[Leetcode][JAVA] Binary Tree Preorder Traversal, Binary Tree Inorder Traversal, Binary Tree Postorder Traversal