单链表有多个next指针就变成树了。
Linked List是特殊化的Tree,Tree是特殊化的Graph。
没有环的图就是树。
树节点
Java
public class TreeNode{
public int val;
public TreeNode left,right;
public TreeNode(int val){
this.val = val;
this.left = null;
this.right = null;
}
}
C++
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
}
二叉树遍历
1.前序:根-左-右
2.中序:左-根-右
3.后序:左-右-根
遍历基本上基于递归的
def preorder(self,root):
if root:
self traverse_path append(root val)
self preorder(root left)
self preorder(root right)
def inorder(self,root):
if root:
self inorder(root left)
self traverse_path append(root val)
self inorder(root right)
def postorder(self,root)
if root:
self postorder(root left)
self postorder(root right)
self traverse_path append(root val)
二叉搜索树Binary Search Tree
二叉搜索树，也称二叉排序树、有序二叉树、排序二叉树，是指一棵空树或者具有下列性质的二叉树:
1.左子树上所有节点的值均小于它的根节点的值；
2.右子树上的所有节点的值均大于它的根节点的值；
3.一次类推:左、右子树也分别为二叉查找树。(这就是重复性！)
中序遍历:升序遍历
1.查询 log2(n)
2.插入新节点(创建) log2(n)
3.删除
二叉树的中序遍历
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
给定一个二叉树，返回它的中序遍历。
输入: [1,null,2,3]
1
2
/
3
输出: [1,3,2]
方法一:递归法
第一种解决方法是使用递归。这是经典的方法，直截了当。我们可以定义一个辅助函数来实现递归。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val = x;
}
}
public class Solution {
@Test
public void testBinaryTree(){
TreeNode root = new TreeNode(1);
TreeNode tree4 = new TreeNode(4);
TreeNode tree5 = new TreeNode(5);
TreeNode tree2 = new TreeNode(2);
TreeNode tree3 = new TreeNode(3);
TreeNode tree6 = new TreeNode(6);
root.left = tree2;
root.right = tree3;
tree2.left = tree4;
tree2.right = tree5;
tree3.left = tree6;
List<Integer> res = inorderTraversal(root);
System.out.printf(res.toString());
}
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
helper(root,res);
return res;
}
public void helper(TreeNode root,ArrayList<Integer> res){
if(root != null){
if(root.left != null){
helper(root.left,res);
}
res.add(root.val);
if(root.right != null){
helper(root.right,res);
}
}
}
}
//输出
[4, 2, 5, 1, 6, 3]
复杂度分析
时间复杂度：O(n)。递归函数 T(n) = 2 * T(n/2)+1。
空间复杂度：最坏情况下需要空间O(n)O(n)，平均情况为O(\log n)O(logn)。
二叉树.png
方法二:基于栈的遍历
public class Solution {
@Test
public void testStack(){
TreeNode root = new TreeNode(1);
TreeNode tree4 = new TreeNode(4);
TreeNode tree5 = new TreeNode(5);
TreeNode tree2 = new TreeNode(2);
TreeNode tree3 = new TreeNode(3);
TreeNode tree6 = new TreeNode(6);
root.left = tree2;
root.right = tree3;
tree2.left = tree4;
tree2.right = tree5;
tree3.left = tree6;
List<Integer> res = inorderTraversal0(root);
System.out.printf(res.toString());
}
public List<Integer> inorderTraversal0(TreeNode root){
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()){
while(curr != null){
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
」
//输出
[4, 2, 5, 1, 6, 3]
复杂度分析
时间复杂度：O(n)O(n)。
空间复杂度：O(n)O(n)。
二叉树的前序遍历
方法一:递归法
class Solution {
@Test
public void testpreorderTravelsal(){
TreeNode root = new TreeNode(1);
TreeNode tree4 = new TreeNode(4);
TreeNode tree5 = new TreeNode(5);
TreeNode tree2 = new TreeNode(2);
TreeNode tree3 = new TreeNode(3);
TreeNode tree6 = new TreeNode(6);
root.left = tree2;
root.right = tree3;
tree2.left = tree4;
tree2.right = tree5;
tree3.left = tree6;
List<Integer> res = preorderTraversal(root);
System.out.printf(res.toString());
}
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
helper0(root,res);
return res;
}
public void helper0(TreeNode root,ArrayList<Integer> res){
if(root != null){
res.add(root.val);
if(root.left!=null){
helper0(root.left,res);
}
if(root.right!=null){
helper0(root.right,res);
}
}
}
}
//输出
[1, 2, 4, 5, 3, 6]
方法二:基于栈的遍历
@Test
public void testPreorderTraversalStack0(){
TreeNode root = new TreeNode(1);
TreeNode tree4 = new TreeNode(4);
TreeNode tree5 = new TreeNode(5);
TreeNode tree2 = new TreeNode(2);
TreeNode tree3 = new TreeNode(3);
TreeNode tree6 = new TreeNode(6);
root.left = tree2;
root.right = tree3;
tree2.left = tree4;
tree2.right = tree5;
tree3.left = tree6;
List<Integer> res = preorderTraversal0(root);
System.out.printf(res.toString());
}
public List<Integer> preorderTraversal0(TreeNode root){
ArrayList<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root;
while(curr != null || !stack.isEmpty()){
while(curr!= null){
res.add(curr.val);
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
curr = curr.right;
}
return res;
}
//输出
[1, 2, 4, 5, 3, 6]
时间复杂度：访问每个节点恰好一次，时间复杂度为 O(N)O(N) ，其中 NN 是节点的个数，也就是树的大小。
空间复杂度：取决于树的结构，最坏情况存储整棵树，因此空间复杂度是 O(N)O(N)。
N叉树的前序遍历
@Test
public void testPreOrder(){
Node root = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
ArrayList<Node> list = new ArrayList<Node>();
list.add(node3);
list.add(node2);
list.add(node4);
root.children = list;
ArrayList<Node> list0 = new ArrayList<Node>();
list.add(node5);
list.add(node6);
node3.children = list0;
List<Integer> list1 = preorder(root);
System.out.println(list1.toString());
}
public List<Integer> preorder(Node root) {
ArrayList<Integer> res = new ArrayList<Integer>();
Node curr = root;
helper(curr,res);
return res;
}
public void helper(Node curr,ArrayList<Integer> res){
if(curr != null){
res.add(curr.val);
if(curr.children != null && curr.children.size()>0){
for(Node node:curr.children){
helper(node,res);
}
}
}
}
//输出
[1, 3, 2, 4, 5, 6]
网友评论