二叉树的基本操作（一）

二叉树的基本操作

• 二叉树的遍历

​ 如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。
LNR：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
LRN：后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点

层序遍历：从二叉树的根节点出发，首先访问第一层的节点，然后从左至右访问第二层的节点，从上至下，以此类推

以上树为例，简单介绍二叉树的遍历实现：

• 前序遍历

根节点－左子树－右子树

前序遍历的结果为： A　B　D　E　H　C　F　G

//前序遍历
   public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.println(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);

   }

• 中序遍历

左子树－根节点－右子树

中序遍历的结果为： D B E 　H A F C G　

// 中序遍历
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.println(root.val+" ");
        inOrder(root.right);
    }

• 后序遍历　

左子树－右子树－根节点

 // 后序遍历
    public void postOrde(TreeNode root){
        if(root == null){
            return;
        }
        postOrde(root.left);
        postOrde(root.right);
        System.out.println(root.val+" ");
    }

• 层序遍历

从根节点出发从左至右，以此类推

层序遍历结果： A 　B 　C 　D 　E 　F　 G 　H

• 使用List存储节点元素进行前序遍历

  public List<Character> preOrder2(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        ret.add(root.val);
        List<Character> leftTree = preOrder2(root.left);
        ret.addAll(leftTree);
        List<Character> rightTree  = preOrder2(root.right);
        ret.addAll(rightTree);
        return ret;
    }

• 获取树中节点的个数

获取树中节点的个数，我们可以采用遍历的方法实现，也可以采用子问题的思路，使用递归的方法，即左子树＋右子树＋根节点（＋１）即可实现

size(root.left) +size(root.right)+1;

     /**
     *  遍历方法
     */
    public static int nodeSize = 0;
    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        nodeSize++;
        size(root.left);
        size(root.left);
        return nodeSize;
    }
    /**
     * 子树相加再加上根节点
     * @param root
     * @return
     */
    public int size2(TreeNode root){
        if(root == null){
            return 0;
        }
        int tmp = size(root.left) +size(root.right)+1;
        return tmp;
    }

• 获取树中叶子节点的个数

获取树中叶子节点的个数，即左子树和右子树都为空时root.left==null&&root.right==null时，左子树上叶子节点+右子树上所有的叶子节点 或者使用临时变量leafSize＋＋；

    /**
     * 获取叶子节点的个数
     * @param root
     * @return
     */
  //子问题思路
    public int getLeafNodeCount(TreeNode root){
        if(root == null){
            return  0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        int tmp = getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
        return tmp;
    }
     //遍历方法
    public static int leafSize = 0;
    public  int getLeafNodeCount2(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null&&root.right == null){
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
        return leafSize;
    }