Skip to content
kaba

二叉树常见思路

算法1 min read

1// Definition for a binary tree node.
2function TreeNode(val, left, right) {
3 this.val = (val===undefined ? 0 : val)
4 this.left = (left===undefined ? null : left)
5 this.right = (right===undefined ? null : right)
6}

算法设计思路:明确一个节点要做的事,剩下的交给框架

1/* 二叉树遍历框架 */
2void traverse(TreeNode root) {
3 // 前序遍历
4 traverse(root.left)
5 // 中序遍历
6 traverse(root.right)
7 // 后序遍历
8}

如:

1// 二叉树所有节点+1
2void plusOne(TreeNode root) {
3 if (root == null) return;
4 root.val += 1;
5
6 plusOne(root.left);
7 plusOne(root.right);
8}
9// 判断两颗二叉树完全相同
10boolean isSameTree(TreeNode root1, TreeNode root2) {
11 // 都为空的话,显然相同
12 if (root1 == null && root2 == null) return true;
13 // 一个为空,一个非空,显然不同
14 if (root1 == null || root2 == null) return false;
15 // 两个都非空,但 val 不一样也不行
16 if (root1.val != root2.val) return false;
17
18 // root1 和 root2 该比的都比完了
19 return isSameTree(root1.left, root2.left)
20 && isSameTree(root1.right, root2.right);
21}

二叉搜索树BST

一个二叉树中,任意节点的值要大于等于左子树所有节点的值,且要小于等于右边子树的所有节点的值 image-20210207201157930

判断BST合法性

1// 递归
2var isValidBST = function (root) {
3 return helper(root, null, null);
4};
5var helper = function (root, min, max) {
6 if (root == null) return true;
7 if (min != null && root.val <= min.val) return false;
8 if (max != null && root.val >= max.val) return false;
9 return helper(root.left, min, root) && helper(root.right, root, max);
10}
11// 中序遍历

在BST中查找一个数是否存在

1var searchBST = function (root, val) {
2 if (!root) return root;
3 if (root.val === val) return root;
4 return root.val < val ? searchBST(root.right, val) : searchBST(root.left, val)
5};

针对BST的遍历框架

1void BST(TreeNode root, int target) {
2 if (root.val == target)
3 // 找到目标,做点什么
4 if (root.val < target)
5 BST(root.right, target);
6 if (root.val > target)
7 BST(root.left, target);
8}

在BST中插入一个数

1var insertIntoBST = function (root, val) {
2 if (root == null) return new TreeNode(val);
3 if (root.val < val)
4 root.right = insertIntoBST(root.right, val)
5 if (root.val > val)
6 root.left = insertIntoBST(root.left, val)
7 return root
8};

在BST中删除一个数

  1. 节点为末端节点,直接删除
  2. 节点只有一个非空节点,让该节点顶替自己的位置
  3. 节点下有两个子节点,找到左子数中最大的或右子数中最小的节点顶替自己
1var deleteNode = function (root, key) {
2 if (root == null) return null;
3 if (root.val == key) {
4 if (root.left == null) return root.right;
5 if (root.right == null) return root.left;
6 const minNode = getMin(root.right);
7 root.val = minNode.val;
8 root.right = deleteNode(root.right, minNode.val);
9 } else if (root.val < key) {
10 root.right = deleteNode(root.right, key);
11 } else if (root.val > key) {
12 root.left = deleteNode(root.left, key);
13 }
14 return root;
15};
16
17var getMin = function (node) {
18 while (node.left !== null) {
19 node = node.left;
20 }
21 return node;
22}

翻转二叉树

1var invertTree = function (root) {
2 if (root == null) return null;
3 let temp = root.left;
4 root.left = root.right;
5 root.right = temp;
6 invertTree(root.left);
7 invertTree(root.right);
8 return root;
9};

填充每个节点的下一侧右侧节点指针

1var connect = function (root) {
2 if (root == null) return null;
3 connectTwoNode(root.left, root.right);
4 return root;
5};
6
7var connectTwoNode = function (node1, node2) {
8 if (node1 == null || node2 == null) return;
9 node1.next = node2;
10 // 相同父节点
11 connectTwoNode(node1.left, node1.right);
12 connectTwoNode(node2.left, node2.right);
13 // 跨越父节点
14 connectTwoNode(node1.right, node2.left);
15}