Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ About Leetcode on Binary Tree Algorithm summary     - Ceph distributed storage system is installed on a CentOS 7.1 (Server)

- Qt signals and slots mechanism (Programming)

- Struts2 configure a static resource files without Struts processing (regular match) (Programming)

- Linux package manager - yum (Linux)

- To install the latest version of the EPEL on CentOS 5.x or 6.x (Linux)

- MySQL 5.7 perfectly distributed transaction support (Database)

- Linux atomic operations and synchronization mechanisms (Programming)

- Vim highlight lookup operation (Linux)

- Use JMS listener Oracle AQ, trigger the execution of Java programs in the database changes (Database)

- How to Install Sticky Notes on Ubuntu and Derivatives (Linux)

- Oracle 12c PDB Analysis (Database)

- How to add a new hard disk without restarting the CentOS 7 / RHEL 7 virtual machine (Linux)

- iptables using summary (Linux)

- Linux system security check notes on performance (Linux)

- C # function (Programming)

- CentOS install Java 1.8 (Linux)

- Install mono offline on CentOS (Server)

- Let MySQL 5.6 support Emoji expression (Database)

- Swift string common method (Programming)

- GNU Linux system variables (sysctl configuration commands) integrated use (Linux)

 
         
  About Leetcode on Binary Tree Algorithm summary
     
  Add Date : 2017-08-31      
         
         
         
  Binary Tree, the structure is very simple, just more complicated than a single list so Diudiu only. Let's take a look at the differences between them on the node:

/ * Single linked list structure * /
struct SingleList {
    int element;
    struct SingleList * next;
};
/ * Binary tree structure * /
struct BinaryTree {
    int element;
    struct BinaryTree * left;
    struct BinaryTree * right;
};
According to the above two structures, we find that a single list node only a pointer to the next node, and there are two binary tree. That single list each node has only one child node, and the binary tree has two children (one of which may be NULL). Knowing this distinction, we know: based on binary tree algorithm than the algorithm based on the difference a single list is a node after each iteration, need to traverse two child nodes, but only need to traverse a single list of child nodes.

This leads to two kinds of traversal methods: breadth-first traversal (BFS) and depth-first traversal (DFS).

For a single linked list is, the BFS and DFS is the same, since each node has only one child node, each node in a next traverse only one choice; but binary tree each node has two child nodes, i.e. traversal order is either it can traverse the child nodes (node, whether left or right node are DFS), also can traverse its sibling nodes. If each time to traverse the child nodes so that DFS; the first traversing each sibling node is BFS.

DFS uses stack structure, bloggers here is the recursive stack to achieve, of course, we can also use the stack to achieve; BFS uses a queue queue.

void dfs (BinaryTree * root) {
    if (NULL == root)
        return;
    dfs (root-> left);
    dfs (root-> right);
}

void bfs (BinaryTree * root) {
    if (NULL == root)
        return;
    queue que;
    que.push ();
    while (! que.empty ()) {
        BinaryTree * pNode = que.front ();
que.pop ();
        if (pNode-> left)
            que.push (pNode-> left);
        if (pNode-> right)
            que.push (pNode-> right);
    }
}
About some algorithms tree, DFS and BFS are generally applicable, but when it comes to the root to leaf path of such problems, it is best to use DFS to achieve. As follows:

1, to a binary tree and a value Sum, all values obtained from root to leaf is equal to Sum of all paths.

Ideas: depth-first search (DFS), and then with the start of each visit from a node to put the node added to the last position of a vec, and subtract the sum is passed to the next node by value after the current point, when about a child node are NULL, and the value equal to the sum, it shows that the node is a leaf node, and from the root to the node path and the Sum, the vec, added to the res; and each return , you need to vec last value is removed, since each node has two child nodes, the path from the root to the leaves and children left the path to the right child leaves is different, all the children left after each visit or children need the right to remove the child from the value of the vec.

/ **
 * Definition for a binary tree node.
 * Struct TreeNode {
 * Int val;
 * TreeNode * left;
 * TreeNode * right;
 * TreeNode (int x): val (x), left (NULL), right (NULL) {}
 *};
 * /
class Solution {
private:
    vector > res;
    vector vec;
    void _pathSum (TreeNode * root, int sum) {
        if (root == NULL)
            return;
        vec.push_back (root-> val);
        if (root-> left == NULL && root-> right == NULL && sum == root-> val) {
            res.push_back (vec);
            return;
        }
        _pathSum (root-> left, sum-root-> val);
        if (root-> left)
            vec.pop_back ();
        _pathSum (root-> right, sum-root-> val);
        if (root-> right)
            vec.pop_back ();
    }
public:
    vector > pathSum (TreeNode * root, int sum) {
        if (NULL == root)
            return res;
        _pathSum (root, sum);
        return res;
    }
};
2, binary conversion

The binary tree:

    4
   / \
  27
 / \ / \
1369
Converted to

     4
   / \
  72
 / \ / \
9631
Thoughts: This can either be used with the DFS BFS, which is to traverse each node, and then you can swap them around children. BFS used here to achieve:

/ **
 * Definition for a binary tree node.
 * Struct TreeNode {
 * Int val;
 * TreeNode * left;
 * TreeNode * right;
 * TreeNode (int x): val (x), left (NULL), right (NULL) {}
 *};
 * /
class Solution {
public:
    TreeNode * invertTree (TreeNode * root) {
        if (NULL == root)
            return NULL;
        queue que;
        que.push (root);
        while (! que.empty ()) {
            TreeNode * pChild = que.front ();
            que.pop ();
            TreeNode * pNode = pChild-> left;
            pChild-> left = pChild-> right;
            pChild-> right = pNode;
            if (pChild-> left)
                que.push (pChild-> left);
            if (pChild-> right)
                que.push (pChild-> right);
        }
        return root;
    }
};
 3, summary

Once you master the DFS and BFS ideas, other algorithms on binary trees are basically similar, when necessary, by drawing to make their own perceptions of what is excellent.
     
         
         
         
  More:      
 
- Debian 7.8 system installation and configuration process (Linux)
- Based on OpenSSL for HTTPS service configuration (Server)
- Ubuntu users to install the system indicator SysPeek 0.3 (Linux)
- HAProxy performance under high concurrency (Server)
- Math objects easily overlooked but very convenient method --JavaScript (Programming)
- 20 Linux commands interview questions and answers (Linux)
- Bash variable expansion modifier (Programming)
- Mass data storage application of MongoDB database (Database)
- 64-bit Oracle Linux recompiled Hadoop-2.2.0 (Server)
- Install VMware Tools in Debian (Linux)
- Elaborate 10-point difference between the new and malloc (Programming)
- Difference LVS three scheduling modes (Server)
- Dockerfile use to build a mirror-based CentOS 7 (Linux)
- Using RAID in Linux: Create a RAID 5 (Linux)
- Summary of Docker mounted directory (Server)
- Using IPFilter bridge filter in the FreeBSD system (Linux)
- CentOS7 install NTFS-3G driver (Linux)
- Oracle table compression Technology Introduction (Database)
- About Samba certification process and permissions (Linux)
- About Hibernate cache, you want the latest data have trouble even session.clear (Database)
     
           
     
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.