讨论/《深度优先搜索》 - 练习:N 叉树的前序遍历/
《深度优先搜索》 - 练习:N 叉树的前序遍历
共 5 个回复
class Solution {
    public List<Integer> preorder(Node root) {
        if (root == null) {
            return Collections.<Integer>emptyList();
        }
        List<Node> stack = new ArrayList<>();
        List<Integer> ret = new ArrayList<>();

        stack.add(root);

        while (!stack.isEmpty()) {
            root = stack.remove(stack.size() - 1);
            ret.add(root.val);
            if (root.children != null && !root.children.isEmpty()) {
                for (int i = root.children.size() - 1; i >= 0; i--) {
                    stack.add(root.children.get(i));
                }
            }
        }
        return ret;
    }
}

JS 递归法


/**
 * @param {Node} root
 * @return {number[]}
 */
var preorder = function(root) {
    let result = [];
    var dfs = function(node) {
      if (node == null) {
        return null;
      }
      if (node.children) {
        result.push(node.val);
        for(let i = 0; i < node.children.length; i++) {
          dfs(node.children[i]);
        }
      } else {
        result.push(node.val);
      }

    }
    dfs(root);
    return result;
    
};
class Solution {
    private static String GO = "GO";
    private static String ADD = "ADD";
    class Command {
        private String code;
        private Node node;
        public Command(String code, Node node){
            this.code = code;
            this.node = node;
        }
    }
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList();
        if(root == null) return res;
        Deque<Command> stack = new LinkedList();
        stack.push(new Command(GO, root));

        while (!stack.isEmpty()){
            Command command = stack.pop();
            if(command.code.equals(ADD)){
                res.add(command.node.val);
            } else{
                for(int i = command.node.children.size() - 1; i >=0; i--) {
                    stack.push(new Command(GO, command.node.children.get(i)));
                }
                stack.push(new Command(ADD, command.node));
            }
        }
        return res;
    }
}
class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> result;
        if(!root)
            return result;
        
        stack<Node*> stk;
        stk.push(root);
        while(!stk.empty()){
            Node* currNode = stk.top();
            stk.pop(); 
            if(currNode){
                for(int i = currNode->children.size()-1; i>=0;i--){
                    stk.push(currNode->children[i]);
                }
                stk.push(currNode);
                stk.push(nullptr);
            }else{
                currNode = stk.top();
                stk.pop();
                result.push_back(currNode->val);
            }
        }
        
        return result;
    }
};
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root : return []
        q = deque([root])
        res = []
        while q:
            cur = q.pop()
            res.append(cur.val)
            for child in cur.children[::-1]:
                if child : 
                    q.append(child)
        return res