二叉树遍历/算法数据结构

六、树

6.1遍历算法

6.1.1前中后序

• 在做递归时，最重要是三步骤

  1. 确定递归函数的返回值和参数

  2. 确定终止条件

  3. 确定单层递归的逻辑

     伪代码
     void travel(cur, vec) {if (cur == null) {return ;}vec.push(cur->middle, vec);  // 递归中节点vec.push(cur->left, vec);    // 递归左节点vec.push(cur->right, vec);   // 递归右节点
     }
     

  • 其实很简单，参数就是要目前遍历节点在哪，返回值也同理，终止条件就是指遍历到null的时候回溯，逻辑不要想复杂，根据顺序移动上述上个递归函数即可

  • 前顺遍历

    class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preorder(root, result);return result;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return; }result.add(root.val);  // 中节点preorder(root.left, result);   // 左子树preorder(root.right, result);  // 右子树}
    }
    

  • 中序遍历

    class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}public void inorder(TreeNode root, List<Integer> res) {if (root == null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
    }
    

  • 后序遍历

    class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();postorder(root, result);return result;}public void postorder(TreeNode root, List<Integer> result) {if (root == null) {return;}postorder(root.left, result);   postorder(root.right, result);result.add(root.val);}
    }
    

  • 其实很简单，根据遍历的顺序摆放遍历顺序和添加元素的顺序，(root.left, result)代表左子树，(root.right, result)代表右子树，(root.val)代表中节点。

  • 递归

  • 前序（要理解遍历的核心，先把中节点塞入，然后根据栈去模拟，先加入右节点然后是左节点，移动到左节点继续加入）

    class Solution {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if (root == null){return res;}stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.pop();res.add(temp.val);if (temp.right != null) {stack.push(temp.right);}if (temp.left != null) {stack.push(temp.left);}}return res;}
    }
    

  • 中序（核心就是每收集一个元素到res数组中，其实都是以中节点的姿态进入，这也对应了为什么if循环为什么要push一个null节点，前中后也只要交换顺序即可）

    class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root != null) stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.peek();if (temp != null) {stack.pop();if (temp.right != null) stack.add(temp.right);stack.push(temp);stack.push(null);if (temp.left != null) stack.add(temp.left);}else {stack.pop();temp = stack.peek();stack.pop();res.add(temp.val);}}return res;}
    }
    

  • 后序（就是前序遍历的左右调换顺序，然后再倒叙结果数组）

    class Solution {public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if (root == null){return res;}stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.pop();res.add(temp.val);if (temp.left != null) {stack.push(temp.left);}if (temp.right != null) {stack.push(temp.right);}}Collections.reverse(res);return res;}
    }
    

6.1.2层序遍历

1. 递归算法，一般递归就是深度优先了，要明确三要素，一般遍历就是参数为当前处理节点+加其它附属条件，循环处理按照顺序（这里是左到右），结束条件都是到底直接返回

   class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {check(root, 0);return res;}public void check(TreeNode temp, int deep) {if (temp == null) {return;}deep++;if (res.size() < deep) {  // 创建数组的条件，不可能预先创建的List<Integer> res1 = new ArrayList<>();res.add(res1);}res.get(deep-1).add(temp.val);  // 注意为deep-1，区分索引和深度的区别check(temp.left, deep);  // 左子树check(temp.right, deep);  // 右子树}
   }
   

2. 迭代，就是按照队列，先进先出，按照层数模拟也就是广度优先遍历

   class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Deque<TreeNode> queue = new ArrayDeque<>();List<List<Integer>> res = new ArrayList<List<Integer>>();  // 结果二维数组if (root != null) {queue.addLast(root);  // 防止root为空}while (!queue.isEmpty()) {int size = queue.size();  // size代表每一层几个元素List<Integer> res1 = new ArrayList<>();while (size > 0) {  // size为0这一层就停止TreeNode temp =  queue.removeFirst();res1.add(temp.val);if (temp.left != null) queue.addLast(temp.left);  // 左节点if (temp.right != null) queue.addLast(temp.right);  // 右节点size--;  // 记得减一}res.add(res1);}return res;}
   }