树的遍历

N叉树的遍历

• N叉树的前序遍历

class Node {
    public int val;
    public List<Node> children;
}
// 迭代法
public List<Integer> preorder(Node root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) {
        return list;
    }
    Stack<Node> stack = new Stack<Node>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node n = stack.pop();
        list.add(n.val);
        if (n.children != null) {
            for (int i = n.children.size() - 1; i >= 0 ; i--) {
                stack.push(n.children.get(i));
            }
        }
    }
    return list;
}
// 递归法
public List<Integer> preorder(Node root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) {
        return list;
    }
    preorder(root, list);
    return list;
}

public void preorder(Node root, List<Integer> list) {
    list.add(root.val);
    if (root.children != null) {
        for (Node c: root.children) {
            preorder(c, list);
        }
    }
}

• N叉树的后序遍历

// 迭代法
public List<Integer> postorder(Node root) {
    LinkedList<Integer> list = new LinkedList<>();
    if (root == null) {
          return list;
    }
    LinkedList<Node> stack = new LinkedList<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node n = stack.pop();
        if (n.children != null) {
            for (Node child: n.children) {
                stack.push(child);
            }
        }
        list.push(n.val);// 插入在list头部
    }
    return list;
}

• N叉树的层序遍历

// 递归法
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> levelOrder(Node root) {
        if (root != null) {
            levelFor(root, 0);
        }
        return list;
    }

    private void levelFor(Node root, int level) {
        if (list.size() < level + 1) {
            list.add(new ArrayList<>());
        }
        list.get(level).add(root.val);
        if (root.children != null) {
            for (Node node: root.children) {
                levelFor(node, level + 1);
            }
        }
    }
}
// 迭代法
public List<List<Integer>> levelOrder(Node root) {
  List<List<Integer>> list = new ArrayList<>();
  if (root == null) {
    return list;
  }
  LinkedList<Node> stack = new LinkedList<>();
  stack.push(root);
  while (!stack.isEmpty()) {
    int size = stack.size();
    List<Integer> level = new ArrayList<>(size);
    while (size-- > 0) {
      Node node = stack.pop();// 弹出栈头部
      level.add(node.val);
      if (node.children != null) {
        for (Node child: node.children) {
          stack.add(child);// 添加到栈尾部 
        }
      }
    }
    list.add(level);
  }
  return list;
}

二叉树

鉴于递归法遍历比较简单，就不重复写了

// 先序遍历
public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  while(root != null || !stack.isEmpty()){
    while(root != null){
      res.add(root.val);
      stack.push(root);
      root = root.left;
    }
    TreeNode cur = stack.pop();
    root = cur.right;
  }
  return res;
}
// 后续遍历，其实就是和先序反着来，优先遍历右子节点
public List<Integer> postorderTraversal(TreeNode root) {
  LinkedList<Integer> res = new LinkedList<>();
  Stack<TreeNode> stack = new Stack<>();
  while(root != null || !stack.isEmpty()){
    while(root != null){
      res.push(root.val);//倒插
      stack.push(root);
      root = root.right;
    }
    TreeNode cur = stack.pop();
    root = cur.left;
  }
  return res;
}
// 中序，和先序一样，就是res.add的地方变了
public List <Integer> inorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  while (root != null || !stack.isEmpty()) {
    while (root != null) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    res.add(root.val);
    root = root.right;
  }
  return res;
}

• 二叉树的层序遍历

// 迭代法
public List<List<Integer>> levelOrder(Node root) {
  List<List<Integer>> list = new ArrayList<>();
  if (root == null) {
    return list;
  }
  LinkedList<Node> stack = new LinkedList<>();
  stack.push(root);
  while (!stack.isEmpty()) {
    List<Integer> level = new ArrayList<>();
    int size = stack.size();
    while (size-- > 0) {
      Node node = stack.pop();
      level.add(node.val);
      if (node.left != null) {
        stack.add(node.left);
      }
      if (node.right != null) {
        stack.add(node.right);
      }
    }
    list.add(level);
  }
  return list;
}

• 二叉树的深度

int depth(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = depth(node.left);
    int right = depth(node.right);
    return Math.max(left, right) + 1;
}