144. Binary Tree Preorder Traversal
Medium
Given the root
of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3] Output: [1,2,3]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Example 4:
Input: root = [1,2] Output: [1,2]
Example 5:
Input: root = [1,null,2] Output: [1,2]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]
. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | /** * 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> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if(root==null) return list; TreeNode p = root; while(p!=null){ if(p.left==null){ list.add(p.val); p = p.right; }else{//p.left!=null; TreeNode prev = p.left; while(prev.right!=null && prev.right!=p) prev = prev.right; if(prev.right==null){ prev.right=p; list.add(p.val); p = p.left; }else{ prev.right=null; p = p.right; } } } return list; } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | /** * 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 { List<Integer> list = new ArrayList<>(); public List<Integer> preorderTraversal(TreeNode root) { helper(root); return list; } void helper(TreeNode node){ if(node==null) return; list.add(node.val); helper(node.left); helper(node.right); } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | /** * 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) { List<Integer> list = new ArrayList<>(); if(root==null) return list; TreeNode H = new TreeNode(0); H.left = root; TreeNode p = H, pred, n1, n2, n3; while(p!=null){ if(p.left==null){ p = p.right; }else{//p.left!=null pred = p.left; while(pred.right!=null && pred.right!=p) pred = pred.right; if(pred.right==null){ pred.right = p; p = p.left; }else{ n1 = p; n2 = n1.left; while(n2!=p){ n3 = n2.right; n2.right = n1; n1 = n2; n2 = n3; } n1 = p; n2 = pred; while(n2!=p){ list.add(n2.val); n3 = n2.right; n2.right = n1; n1 = n2; n2 = n3; } pred.right = null; p = p.right; } } } return list; } } |
No comments:
Post a Comment