LeetCode-二叉树

概述

树是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。树的每一个节点有一个值和一个包含所有子节点的列表，二叉树是一种更为典型的树状结构，每个节点最多有两个子树的树结构，称作左子树和右子树。

树的遍历

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

     F
    /    /     B     G
 / \     A   D     I
   / \   /
  C   E H

F->B->A-D-C-E->G->I->H

中序遍历

中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树，对于二叉搜索树，可以通过中序遍历得到一个递增的有序序列。

     F
    /    /     B     G
 / \     A   D     I
   / \   /
  C   E H

A->B->C->D->E->F->G->H->I

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

     F
    /    /     B     G
 / \     A   D     I
   / \   /
  C   E H

A-C->E->D->B->H->I->G->F

值得注意的是，删除树中的节点时，删除过程将按照后序遍历的顺序进行，也就是说，删除一个节点时，首先删除它的左节点和它的右节点，然后删除节点本身。后序在数学表达中广泛使用，例如AST

     +
    /    /     *     5
 / 4   -
   /   7   2

使用中序遍历可以轻松的构建原始表达式(4*(7-2))+5，使用后序遍历可以便捷的计算该表达式，每遇到一个操作符，可以从栈中弹出栈顶的两个元素，计算结果返回栈中。

LeetCode-二叉树

原文：https://www.cnblogs.com/edifyX/p/13533951.html