树

Introduction

遍历树的三种方式

1.Pre-order Traversal 先序遍历（根左右）

先序遍历是首先访问根。然后遍历左侧的子树。最后，遍历右侧的子树。

先序遍历.png

先序遍历 代码递归遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null){
            return result;
        }
        postorder(result,root);
        return result;
    }
    
    public void postorder(List<Integer> result,TreeNode root){
        if(root != null){
            result.add(root.val);
            if(root.left != null){
              postorder(result,root.left);
            }
            if(root.right != null){
                postorder(result,root.right);
            }
            
        }
    }
}

2.In-order Traversal 中序遍历 (左根右)

中序遍历首先遍历左边的子树。然后访问根目录。最后，遍历右侧的子树。

中序遍历.png

中序遍历 代码递归遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public List<Integer> inorderTraversal(TreeNode root) {
 List<Integer> result = new ArrayList<Integer>();
 if(root == null){
 return result;
 }
 postorder(result,root);
 return result;
 }

 public void postorder(List<Integer> result,TreeNode root){
 if(root != null){
 result.add(root.val);
 if(root.left != null){
 postorder(result,root.left);
 }
 if(root.right != null){
 postorder(result,root.right);
 }

 }
 }
}

通常，对于二叉搜索树，我们可以使用按顺序遍历以排序顺序检索所有数据。

3.Post-order Traversal 后序遍历 （左右根）

后序遍历首先遍历左侧的子树。然后遍历右边的子树。最后，访问根。

后序遍历.png

后序遍历 代码递归遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public List<Integer> postorderTraversal(TreeNode root) {
 List<Integer> result = new ArrayList<Integer>();
 if(root == null){
 return result;
 }
 postorder(result,root);
 return result;
 }

 public void postorder(List<Integer> result,TreeNode root){
 if(root != null){
 result.add(root.val);
 if(root.left != null){
 postorder(result,root.left);
 }
 if(root.right != null){
 postorder(result,root.right);
 }

 }
 }
}

值得注意的是，当您删除树中的节点时，删除过程将按照后续顺序进行。也就是说，当你删除一个节点时，你将删除它的左边的子节点和它的右边的子节点，然后删除节点本身。

4.Level-order Traversal

水平顺序遍历是逐层遍历树。Breadth-First Search是一种在数据结构（如树或图）中遍历或搜索的算法。

该算法从一个根节点开始，并首先访问节点本身。然后遍历它的邻居，遍历它的二级邻居，遍历它的三级邻居，等等。

水平顺序遍历.png

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public List<List<Integer>> levelOrder(TreeNode root) {
 List<List<Integer>> result = new ArrayList<List<Integer>>();
 helper(result,root,0);
 return result;
 }

 public void helper(List<List<Integer>> result,TreeNode root,int level){

 if(root == null){
 return;
 }

 if(result.size() <  level + 1){
 result.add(new ArrayList<Integer>()); //说明还要添加一行
 }
 result.get(level).add(root.val);
 helper(result,root.left,level+1);
 helper(result,root.right,level+1);
 }

}