先来明确下树的概念：明确的父子关系
正确的示例：
错误的示例：
几个名词：
节点：线两端的点即节点
根节点：无父节点的节点
叶子节点：无子节点的节点
几个概念：
高度：从下到上，从0计数，根节点最高
深度：从上到下，从0计数，根节点为0
层：从上到下，从1计数，根节点为第一层
特殊的树，二叉树，二叉树又分为普通二叉树、满二叉树，完全二叉树
普通二叉树：每个节点最多两个字节点。
满二叉树：除了叶子节点，每个节点都有左右两个子节点，所有叶子节点在同一层级。
完全二叉树：从根节点开始，从上到下，从左往右，依次填满节点形成的二叉树。
二叉树的遍历：
前序遍历：根节点-左子树-右子树
中序遍历：左子树-根节点-右子树
后续遍历：左子树-右子树-根节点
示例：
前序遍历：A-B-D-E-C-F-G
中序遍历：D-B-E-A-F-C-G
后续遍历：D-E-B-F-G-C-A
Leetcode练习题：
题二叉树前序遍历
classSolution{publicListIntegerpreorderTraversal(TreeNoderoot){ListIntegerresultList=newArrayList();if(root==null){returnresultList;}//将根节点的值加入返回列表resultList.add(root.val);//如果左子节点不为空，前序遍历左子节点if(root.left!=null){resultList.addAll(preorderTraversal(root.left));}//如果右子节点不为空，前序遍历右子节点if(root.right!=null){resultList.addAll(preorderTraversal(root.right));}returnresultList;}}
94题二叉树中序遍历
classSolution{publicListIntegerinorderTraversal(TreeNoderoot){ListIntegerresultList=newArrayList();if(root==null){returnresultList;}//如果左子节点不为空，中序遍历左子节点if(root.left!=null){resultList.addAll(inorderTraversal(root.left));}//将根节点的值加入返回列表resultList.add(root.val);//如果右子节点不为空，中序遍历右子节点if(root.right!=null){resultList.addAll(inorderTraversal(root.right));}returnresultList;}}
题二叉树后序遍历
classSolution{publicListIntegerpostorderTraversal(TreeNoderoot){ListIntegerresultList=newArrayList();if(root==null){returnresultList;}//如果左子节点不为空，后序遍历左子节点if(root.left!=null){resultList.addAll(postorderTraversal(root.left));}//如果右子节点不为空，后序遍历右子节点if(root.right!=null){resultList.addAll(postorderTraversal(root.right));}//将根节点的值加入返回列表resultList.add(root.val);returnresultList;}}预览时标签不可点收录于话题#个上一篇下一篇