Last active
September 29, 2020 02:25
-
-
Save zhanglintc/2d1b4d5f92090516541d0cc5b76d10d4 to your computer and use it in GitHub Desktop.
preorderTraversal, inorderTraversal, postorderTraversal
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 二叉树前中后序遍历统一写法: | |
| // https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/bang-ni-dui-er-cha-shu-bu-zai-mi-mang-che-di-chi-t/ | |
| class Solution { | |
| // 前序遍历 | |
| public List<Integer> preorderTraversal(TreeNode root) { | |
| if (root == null) return new LinkedList<>(); | |
| List<Integer> res = new LinkedList<>(); | |
| Stack<TreeNode> st = new Stack<>(); | |
| st.push(root); | |
| while (!st.isEmpty()) { | |
| TreeNode node = st.pop(); | |
| if (node != null) { | |
| if (node.right != null) st.push(node.right); // 右 | |
| if (node.left != null) st.push(node.left); // 左 | |
| st.push(node); // 中 | |
| st.push(null); | |
| } | |
| else { | |
| res.add(st.pop().val); | |
| } | |
| } | |
| return res; | |
| } | |
| // 中序遍历 | |
| public List<Integer> inorderTraversal(TreeNode root) { | |
| if (root == null) return new LinkedList<>(); | |
| List<Integer> res = new LinkedList<>(); | |
| Stack<TreeNode> st = new Stack<>(); | |
| st.push(root); | |
| while (!st.isEmpty()) { | |
| TreeNode node = st.pop(); | |
| if (node != null) { | |
| if (node.right != null) st.push(node.right); // 右 | |
| st.push(node); // 中 | |
| st.push(null); | |
| if (node.left != null) st.push(node.left); // 左 | |
| } | |
| else { | |
| res.add(st.pop().val); | |
| } | |
| } | |
| return res; | |
| } | |
| // 后序遍历 | |
| public List<Integer> postorderTraversal(TreeNode root) { | |
| if (root == null) return new LinkedList<>(); | |
| List<Integer> res = new LinkedList<>(); | |
| Stack<TreeNode> st = new Stack<>(); | |
| st.push(root); | |
| while (!st.isEmpty()) { | |
| TreeNode node = st.pop(); | |
| if (node != null) { | |
| st.push(node); // 中 | |
| st.push(null); | |
| if (node.right != null) st.push(node.right); // 右 | |
| if (node.left != null) st.push(node.left); // 左 | |
| } | |
| else { | |
| res.add(st.pop().val); | |
| } | |
| } | |
| return res; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment