二叉树

知识点

二叉树遍历

前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树

中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树

后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点

注意点

• 以根访问顺序决定是什么遍历

• 左子树都是优先右子树

//二叉树的数据结构
class TreeNode {
  int? val;
  TreeNode? left;
  TreeNode? right;
}

递归

void preorderDFS(TreeNode? root) {
  if (root == null) {
    return;
  }
  //前序遍历---输出放在前面 
  //print('${root.val}');
  preorderDFS(root.left);
  //中序遍历---输出放在中间 
  //print('${root.val}');
  preorderDFS(root.right);
  //后续遍历---输出放在后面 
  //print('${root.val}');
}

前序非递归

List<TreeNode?> preordeerTravesal(TreeNode? root) {
  if (root == null) {
    return [];
  }
  List<TreeNode?> results = [];
  List<TreeNode?> stack = [];

  TreeNode? node = root;

  while (stack.isNotEmpty || node != null) {
    //把最左边的一排数字加入 栈中
    while (node != null) {
      stack.add(node);
      results.add(node);
      node = node.left;
    }
    //移除栈顶元素
    node = stack.removeLast();
    //访问栈顶元素的右子树
    node = node?.right;
  }

  return results;
}

中序非递归

List<TreeNode?> inordeerTravesal(TreeNode? root) {
  if (root == null) {
    return [];
  }
  List<TreeNode?> results = [];
  List<TreeNode?> stack = [];

  TreeNode? node = root;

  while (stack.isNotEmpty || node != null) {
    while (node != null) {
      stack.add(node);
      node = node.left;
    }

    node = stack.removeLast();
    results.add(node);//这个放置的地方和前序遍历进行比较
    node = node?.right;
  }

  return results;
}

后序非递归

后序遍历其实就是将前序遍历反转就行了。

List<TreeNode?> lastorderTravesal(TreeNode? root) {
  return preordeerTravesal(root).reversed.toList();
}

二叉树的层次遍历(BFS)

void bfs(TreeNode? root){
  if(root == null) {
    return;
  }
  
  List<TreeNode> queue = [];
  queue.add(root);
  
  while(queue.isNotEmpty) {
    var length = queue.length;
    //一层一层的移除元素
    for(var i = 0;i < length; i++) {
      var node = queue.removeAt(0);
      if(node.left != null) {
        queue.add(node.left!);
      }
      if(node.right != null) {
        queue.add(node.right!);
      }
    }
  }
}

常见题目示例

maximum-depth-of-binary-tree

maximum-depth-of-binary-tree

给定一个二叉树，找出其最大深度。

思路：典型的层次遍历的题型

int maxDepth(TreeNode? root){
  if(root == null) {
    return;
  }
  
  List<TreeNode> queue = [];
  queue.add(root);
  var result = 0;
  while(queue.isNotEmpty) {
    var length = queue.length;
    for(var i = 0;i < length; i++) {
      var node = queue.removeLast();
      if(node.left != null) {
        queue.add(node.left!);
      }
      if(node.right != null) {
        queue.add(node.right!);
      }
    }
    result += 1
  }
  return result;
}

balanced-binary-tree

balanced-binary-tree

给定一个二叉树，判断它是否是高度平衡的二叉树。

思路：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1， 因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据， 所以用-1 表示不平衡，>0 表示树高度（二义性：一个变量有两种含义）。

bool isBalanced(TreeNode? root) {
  return getHeight(root) != -1;
}

int getHeight(TreeNode? root) {
  if (root == null) {
    return 0;
  }

  int leftHeight = getHeight(root.left);
  if (leftHeight == -1) { // 左子树不平衡，直接返回 -1
    return -1;
  }

  int rightHeight = getHeight(root.right);
  if (rightHeight == -1) { // 右子树不平衡，直接返回 -1
    return -1;
  }

  if ((leftHeight - rightHeight).abs() > 1) { // 左右子树高度差超过 1，不平衡
    return -1;
  }

  return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; // 返回节点高度
}

binary-tree-maximum-path-sum

binary-tree-maximum-path-sum

给定一个非空二叉树，返回其最大路径和。

思路：分治法，分为三种情况：左子树最大路径和最大，右子树最大路径和最大，左右子树最大加根节点最大，需要保存两个变量：一个保存子树最大路径和，一个保存左右加根节点和，然后比较这个两个变量选择最大值即可

class Solution {
  int ret = -1000000;
  int maxPathSum(TreeNode? root) {
    helper(root);
    return ret;
  }

  int helper(TreeNode? node) {
    if (node == null) {
      return 0;
    }
    int left = max(0, helper(node.left));
    int right = max(0, helper(node.right));
    ret = max(ret, node.val! + left + right);
    return max(left, right) + node.val!;
  }
}

lowest-common-ancestor-of-a-binary-tree

lowest-common-ancestor-of-a-binary-tree

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点

  TreeNode? lowestCommonAncestor(TreeNode? root, TreeNode? p, TreeNode? q) {
    if (root == null) {
      return root;
    }
    if (root == p || root == q) {
      return root;
    }

    TreeNode? left = lowestCommonAncestor(root.left, p, q);
    TreeNode? right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) {
      return root;
    }
    if (left != null) {
      return left;
    }
    if (right != null) {
      return right;
    }
    return null;
  }

BFS 层次应用

binary-tree-level-order-traversal

binary-tree-level-order-traversal

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）

思路：用一个队列记录一层的元素，然后扫描这一层元素添加下一层元素到队列（一个数进去出来一次，所以复杂度 O(logN)）

  List<List<int>> levelOrder(TreeNode? root) {
    List<List<int>> results = [];
    if (root == null) {
      return results;
    }
    List<TreeNode> queue = [];
    queue.add(root);
    while (queue.isNotEmpty) {
      int length = queue.length;
      List<int> temp = [];
      for (var i = 0; i < length; i++) {
        TreeNode node = queue.removeAt(0);
        temp.add(node.val!);
        if (node.left != null) {
          queue.add(node.left!);
        }
        if (node.right != null) {
          queue.add(node.right!);
        }
      }
      results.add(temp);
    }
    return results;
  }

binary-tree-level-order-traversal-ii

binary-tree-level-order-traversal-ii

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路：在层级遍历的基础上，翻转一下结果即可

  List<List<int>> levelOrderBottom(TreeNode? root) {
    List<List<int>> results = [];
    if (root == null) {
      return results;
    }
    List<TreeNode> queue = [];
    queue.add(root);
    while (queue.isNotEmpty) {
      int length = queue.length;
      List<int> temp = [];
      for (var i = 0; i < length; i++) {
        TreeNode node = queue.removeAt(0);
        temp.add(node.val!);
        if (node.left != null) {
          queue.add(node.left!);
        }
        if (node.right != null) {
          queue.add(node.right!);
        }
      }
      results.add(temp);
    }
    return results.reversed.toList();
  }

binary-tree-zigzag-level-order-traversal

binary-tree-zigzag-level-order-traversal

给定一个二叉树，返回其节点值的锯齿形层次遍历。Z 字形遍历

  List<List<int>> levelOrder(TreeNode? root) {
    List<List<int>> results = [];
    if (root == null) {
      return results;
    }
    List<TreeNode> queue = [];
    queue.add(root);
    while (queue.isNotEmpty) {
      int length = queue.length;
      List<int> temp = [];
      for (var i = 0; i < length; i++) {
        TreeNode node = queue.removeAt(0);
        temp.add(node.val!);
        if (node.left != null) {
          queue.add(node.left!);
        }
        if (node.right != null) {
          queue.add(node.right!);
        }
      }
      results.add(temp);
    }
    List<List<int>> temp = [];
    for (var i = 0; i < results.length; i++) {
      if (i % 2 == 0) {
        temp.add(results[i]);
      } else {
        temp.add(results[i].reversed.toList());
      }
    }
    return temp;
  }

二叉搜索树应用

validate-binary-search-tree

validate-binary-search-tree

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

中序遍历，检查结果列表是否已经有序

class Solution {
  int ret = -100000000000;//取一个最小整数
  bool result = true;

  bool isValidBST(TreeNode? root) {
    dfs(root);
    return result;
  }

  void dfs(TreeNode? root) {
    if (root == null) {
      return;
    }
    dfs(root.left);
    if (root.val! <= ret) {
      result = false;
      return;
    }
    ret = root.val!;
    dfs(root.right);
  }
}

insert-into-a-binary-search-tree

insert-into-a-binary-search-tree

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。

思路：找到最后一个叶子节点满足插入条件即可

// DFS查找插入位置
  TreeNode? insertIntoBST(TreeNode? root, int val) {
    if (root == null) {
      TreeNode? node = TreeNode()..val = val;
      return node;
    }
    if (root.val! > val) {
      root.left = insertIntoBST(root.left, val);
    } else {
      root.right = insertIntoBST(root.right, val);
    }
    return root;
  }

总结

• 掌握二叉树递归与非递归遍历

• 理解 DFS 前序遍历与分治法

• 理解 BFS 层次遍历

练习

• maximum-depth-of-binary-tree

• balanced-binary-tree

• binary-tree-maximum-path-sum

• lowest-common-ancestor-of-a-binary-tree

• binary-tree-level-order-traversal

• binary-tree-level-order-traversal-ii

• binary-tree-zigzag-level-order-traversal

• validate-binary-search-tree

• insert-into-a-binary-search-tree