求给定的二叉树的前序遍历。
例如:
给定的二叉树为{1,#,2,3},
返回:[1,2,3].
备注;用递归来解这道题很简单,你可以给出迭代的解法么?
如果你不明白{1,#,2,3}的含义,点击查看相关信息
import java.util.*; public class Solution { ArrayList<Integer> list = new ArrayList<Integer>(); public ArrayList<Integer> preorderTraversal(TreeNode root) { if(root == null) return list; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while(!stack.isEmpty()){ TreeNode temp = stack.pop(); list.add(temp.val); if(temp.right != null) stack.push(temp.right); if(temp.left != null) stack.push(temp.left); } return list; } }
class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> res; stack<TreeNode *> s; if (root == NULL){ return res; } s.push(root); while (!s.empty()){ TreeNode *cur = s.top(); s.pop(); res.push_back(cur->val); if (cur->right!=NULL) s.push(cur->right); if (cur->left!=NULL) s.push(cur->left); } return res; } };
//栈实现先序遍历 vector<int> preorderTraversal(TreeNode *root) { vector<int> preorder; stack<TreeNode*> st; TreeNode *p=root; while(p||!st.empty()){ if(p){ preorder.push_back(p->val); st.push(p); p=p->left; } else{ p=st.top(); st.pop(); p=p->right; } } return preorder; }
import java.util.ArrayList;
import java.util.Stack;
// 使用栈的思想来模拟递归
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<Integer>();
}
ArrayList<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.add(root);
while (!stack.isEmpty()) {
TreeNode tmp = stack.pop();
result.add(tmp.val);
if (tmp.right != null) {
stack.add(tmp.right);
}
if (tmp.left != null) {
stack.add(tmp.left);
}
}
return result;
}
}
public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); Deque<TreeNode> stack = new LinkedList<TreeNode>(); TreeNode x = root; while(true){ if(x==null){ if(stack.isEmpty()){ return list; } x = stack.pop().right; }else{ stack.push(x); list.add(x.val); x = x.left; } } }
import java.util.*; /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> ret = new ArrayList<>(); if (root == null) { return ret; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); ret.add(node.val); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return ret; } }
前序遍历的迭代算法关键在于:设置一个栈,每次将节点的右孩子压入栈中,当遍历完根节点和左子树,便从栈中弹出右子树,继续循环深入
class Solution { public: vector<int> ans; vector<int> preorderTraversal(TreeNode *root) { if (root == NULL) return ans; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode *top = st.top(); st.pop(); ans.push_back(top->val); if (top->right != NULL) { st.push(top->right); } if (top->left != NULL) { st.push(top->left); } } return ans; } };
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> res; if(root==nullptr) return res; stack<TreeNode *> stackNode; TreeNode * leftNode=root; while(leftNode!=nullptr) { res.push_back(leftNode->val); stackNode.push(leftNode); leftNode=leftNode->left; } while(!stackNode.empty()) { TreeNode *p=stackNode.top(); stackNode.pop(); if(p->right!=nullptr) { TreeNode * q=p->right; while(q!=nullptr) { res.push_back(q->val); stackNode.push(q); q=q->left; } } } return res; } };
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?
同上题,只需要稍微换一下位置即可,十分方便。
import java.util.*;
class Command{
public String str;
public TreeNode node;
public Command(String str,TreeNode node){
this.str = str;
this.node = node;
}
}
public class Solution {
public ArrayList preorderTraversal(TreeNode root) {
ArrayList res = new ArrayList();
if(root == null){
return res;
}
Stack stack = new Stack();
stack.push(new Command("go",root));
while(!stack.isEmpty()){
Command c = stack.pop();
if(c.str == "print"){
res.add(c.node.val);
}else{
if(c.node.right != null){
stack.push(new Command("go",c.node.right));
}
if(c.node.left != null){
stack.push(new Command("go",c.node.left));
}
stack.push(new Command("print",c.node));
}
}
return res;
}
}
import java.util.ArrayList; import java.util.Stack; public class Solution { public ArrayList<integer> preorderTraversal(TreeNode root) { ArrayList<integer> r = new ArrayList<>(); if (root != null) { Stack<treenode> s = new Stack<>(); TreeNode p = null; s.push(root); while (!s.empty()) { p = s.pop(); r.add(p.val); if (p.right != null) s.push(p.right); if (p.left != null) s.push(p.left); } } return r; } }
import java.util.Stack; import java.util.ArrayList; public class Solution { public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> s = new Stack<TreeNode>(); while(root!=null || !s.isEmpty()){ while(root!=null){ s.push(root.right); list.add(root.val); root = root.left; } root = s.pop(); } return list; } }
import java.util.*; public class Solution { ArrayList<Integer> arr=new ArrayList<>(); public ArrayList<Integer> preorderTraversal(TreeNode root) { if(root==null) return arr; isPre(root); return arr; } public void isPre(TreeNode root){ if(root!=null){ arr.add(root.val); isPre(root.left); isPre(root.right); } } }
import java.util.Stack; import java.util.ArrayList; public class Solution { public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); if(root==null){ return list; } TreeNode t = root; Stack<TreeNode> st = new Stack<TreeNode>(); while(t!=null || !st.empty()){ while(t!=null){ list.add(t.val); st.push(t); t = t.left; } if(!st.empty()){ t = st.pop(); t = t.right; } } return list; } }
import java.util.*;//还是递归好用 public class Solution { public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> al = new ArrayList<Integer>(); if(root==null)return al; al.add(root.val); al.addAll(preorderTraversal(root.left)); al.addAll(preorderTraversal(root.right)); return al; } }
/* * 思路: 可以动手实验一下哦! * 1.申请1个栈,记为stack,然后将头节点head压入stack中。 * 2.从stack中弹出的节点记为cur,然后记录cur节点的值(或是打印,根据题目需要),再将cur的右孩子节点压入栈中(如果右孩子不为空) * 最后再将cur的左孩子(如果不为空),压入stack中。 * 3.不断重复,步骤2,直到stack为空,过程停止。 */ import java.util.ArrayList; import java.util.Stack; public class BinaryTreePreOrderTraversal { public ArrayList<Integer> preorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); ArrayList<Integer> res = new ArrayList<>(); if (root != null) { stack.push(root); while(!stack.isEmpty()) { TreeNode cur = stack.pop(); res.add(cur.val); if (cur.right != null) { stack.push(cur.right); } if (cur.left != null) { stack.push(cur.left); } } } return res; } }