type TreeNode struct { Val int Left *TreeNode Right *TreeNode }
funcpreorderTraversal(root *TreeNode) []int { var ( stack = make([]*TreeNode,0,10) curr = root res = make([]int,0,10) ) for curr!=nil || len(stack) != 0{ if curr!=nil{ res = append(res,curr.Val) stack = append(stack,curr) curr = curr.Left }else{ curr = stack[len(stack)-1] stack = stack[:len(stack)-1] curr = curr.Right } } return res }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
public List<Integer> preorderTraversal(TreeNode root){ List<Integer> res = new ArrayList<>(); Stack<TreeNode> s = new Stack<>(); TreeNode cur = root; while(cur != null || !s.isEmpty()){ if(cur != null){ res.add(cur.val); // root s.push(cur); cur = cur.left; // left }else{ cur = s.pop(); cur = cur.right; // right } } return res; }
中序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
public List<Integer> inorderTraversal(TreeNode root){ List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while(cur != null || !stack.isEmpty()){ if(cur != null){ stack.push(cur); cur = cur.left; // left }else{ cur = stack.pop(); res.add(cur.val); // root cur = cur.right; // right } } return res; }